20210805님의 코드:

import io, os, sys
from typing import List


def main() -> None:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    for _ in range(int(input())):
        num_nodes, num_edges = map(int, input().split())
        graph: List[List[int]] = [[] for _ in range(num_nodes)]
        for _ in range(num_edges):
            u, v = map(int, input().split())
            u -= 1
            v -= 1
            graph[u].append(v)
            graph[v].append(u)
        print("YES" if is_bipartite(num_nodes, graph) else "NO")


def is_bipartite(num_nodes: int, graph: List[List[int]]) -> bool:
    stack: List[int] = []
    colors: List[int] = [-1] * num_nodes
    for node in range(num_nodes):
        if colors[node] == -1:
            colors[node] = 0
            stack.append(node)
            while stack:
                u = stack.pop()
                for v in graph[u]:
                    if colors[v] == -1:
                        colors[v] = 1 - colors[u]
                        stack.append(v)
                    elif colors[v] == colors[u]:
                        return False
    return True


if __name__ == "__main__":
    sys.exit(main())  # type: ignore[func-returns-value]

메모리 약 66MB, 시간 1000ms

Things to Note

1. io 모듈의 BytesIO

스트림 작업을 위한 io 모듈.
버퍼링 된 I/O 스트림은 원시 I/O보다 I/O 장치에 대한 더 고수준의 인터페이스를 제공합니다. 인 메모리 바이트 버퍼를 사용하는 바이너리 스트림. BufferedIOBase를 상속합니다. close() 메서드가 호출될 때 버퍼가 폐기됩니다. 선택적 인자 initial_bytes는 초기 데이터를 포함하는 바이트열류 객체입니다.
class io.BytesIO(initial_bytes=b'')

os.read(0, os.fstat(0).st_size))

os 모듈 : 이 모듈은 운영 체제 종속 기능을 사용하는 이식성 있는 방법을 제공합니다. 파일을 읽거나 쓰고 싶으면 open()을 보세요, 경로를 조작하려면 os.path 모듈을 보시고, 명령 줄에서 주어진 모든 파일의 모든 줄을 읽으려면 fileinput 모듈을 보십시오. 임시 파일과 디렉터리를 만들려면 tempfile 모듈을 보시고, 고수준의 파일과 디렉터리 처리는 shutil 모듈을 보십시오.

read

os.read(fd, n, /) : 파일 기술자 fd에서 최대 n 바이트를 읽습니다. 읽어 들인 바이트를 포함하는 바이트열을 돌려줍니다. fd 에 의해 참조된 파일의 끝에 도달하면, 빈 바이트열 객체가 반환됩니다.

더 빠른가? 0은 인풋을 받기 위함일거고, n 인자로 os.fstat(0).st_size를 줬다.

os.fstat(0).st_size

파일 기술자 fd 의 상태를 가져옵니다. stat_result 객체를 반환합니다.

stat_result 객체

어트리뷰트가 stat 구조체의 멤버와 대략 일치하는 객체. os.stat(), os.fstat() 및 os.lstat()의 결과로 사용됩니다.

st_size 어트리뷰트

일반 파일 또는 심볼릭 링크면, 바이트 단위의 파일의 크기. 심볼릭 링크의 크기는 포함하고 있는 경로명의 길이이며, 끝나는 널 바이트는 포함하지 않습니다.

출처: 파이썬 공식 문서(3.11.2)

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

  1. BytesIO : 바이트열류 객체를 받는다.
  2. os.read : 0은 stdin, os.fstat(0).st_size는 stdin의 바이트 단위 파일의 크기
  3. readline : 한 줄씩 읽기

2. 떨어져 있는 그래프 확인

그냥 노드들을 다 훑었다 : (for node in range(num_nodes): )

3. 스택을 사용

현재 노드의 색깔은 이전 노드의 색깔과 다르게 칠한다는 조건으로 스택을 사용할 수 있다.

4. 포매팅

깔끔한 코드다. 굉장한 실력자일 것 같은 생각이 든다.

내 코드:

1. 재귀함수 사용

import sys


input = sys.stdin.readline

def bfs(q: list):
    while q:
        u, idx = q.pop()
        for v in graph[u]:
            if visited[v] == -1:
                q.append((v, idx^1))
                visited[v] = idx^1
                s.discard(v)
            elif visited[v] == idx:
                print('NO')
                return
    if s:
        x = s.pop()
        visited[x] = 0
        bfs([(x, 0)])
    else:
        print('YES')
        return


for tc in range(int(input())):
    V, E = map(int, input().split())   # 정점의 개수, 간선의 개수
    graph = [[] for _ in range(V+1)]
    s = set()   # 모든 그래프가 탐색되었는지 확인하기 위한 세트
    visited = [-1] * (V+1)   # 방문 표시할 리스트
    
    # 그래프 그리기
    for _ in range(E):
        u, v = map(int, input().split())
        s.update([u, v])
        graph[u].append(v)
        graph[v].append(u)
    
    # 전처리 및 bfs 수행
    x = s.pop()
    visited[x] = 0
    bfs([(x, 0)])

메모리 약 53MB, 시간 1644ms

2. 반복문 사용

import sys
from collections import deque
input = sys.stdin.readline
def bfs(q: deque):
    while q:
        u, idx = q.popleft()
        for v in graph[u]:
            if visited[v] == -1:
                q.append((v, idx^1))
                visited[v] = idx^1
                s.discard(v)
            elif visited[v] == idx:
                print('NO')
                return False
    return True

for tc in range(int(input())):
    V, E = map(int, input().split())   # 정점의 개수, 간선의 개수
    graph = [[] for _ in range(V+1)]
    s = set()
    visited = [-1 for _ in range(V+1)]
    for _ in range(E):
        u, v = map(int, input().split())
        s.update([u, v])
        graph[u].append(v)
        graph[v].append(u)
    
    while True:
        x = s.pop()
        visited[x] = 0
        f = bfs(deque([(x, 0)]))
        if s and f:   # set이 아직 비지 않았으나 f == True일 때 -> 아직 탐색하지 않은 트리가 있다.
            continue
        elif f:   # set이 비었지만 f == True일 때 -> 다 탐색
            print('YES')   # 'YES' 출력 후 종료
            break
        else:   # set이 비었고 f == False일 경우 'NO'가 이미 출력되었음.
            break

메모리 약 54MB, 시간 1540ms

확실히 반복문을 사용한 코드가 빠르다.

import io, os, sys


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def is_bipartite(ls: list):
    while ls:
        u, idx = ls.pop()
        for v in graph[u]:
            if visited[v] == -1:
                ls.append((v, idx^1))
                visited[v] = idx^1
                s.discard(v)
            elif visited[v] == idx:
                print('NO')
                return
    if s:
        x = s.pop()
        visited[x] = 0
        is_bipartite([(x, 0)])
    else:
        print('YES')
        return


for tc in range(int(input())):
    V, E = map(int, input().split())   # 정점의 개수, 간선의 개수
    graph = [[] for _ in range(V+1)]
    s = set()   # 모든 그래프가 탐색되었는지 확인하기 위한 세트
    visited = [-1] * (V+1)   # 방문 표시할 리스트
    
    # 그래프 그리기
    for _ in range(E):
        u, v = map(int, input().split())
        s.update([u, v])
        graph[u].append(v)
        graph[v].append(u)
    
    # 전처리 및 bfs 수행
    x = s.pop()
    visited[x] = 0
    is_bipartite([(x, 0)])

메모리 약 64MB, 시간 1288ms

profile
이토록 멋진 휴식!

0개의 댓글