기록을 위해 남김

반례들:

13
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
3 1
1 2
5 2
1 2
2 3
4 2
1 2
3 4
4 3
1 4
2 3
3 4
5 4
1 2
3 4
3 5
4 5
6 4
1 2
2 4
4 5
5 6
6 6
1 3
3 4
4 2
2 5
5 6
6 1
4 4
1 2
2 3
3 4
4 1
4 4
1 2
2 3
3 4
4 2
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 1

정답:

1. YES
2. NO
3. YES
4. YES
5. YES
6. YES
7. NO
8. YES
9. YES
10. YES
11. NO
12. NO
13. NO

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

1. Bitwise XOR 연산자를 사용해 노드들을 그룹지음.
2. 세트를 사용해 아직 탐색하지 않은, 떨어져 있는 그래프가 있는지 판단.

TIL

파이썬 set 메써드 discard와 remove에 대해 배웠다. discard는 set 안에 버리려는 원소가 없어도 오류를 반환하지 않지만 remove는 KeyError를 반환한다.