-
Notifications
You must be signed in to change notification settings - Fork 0
/
이분 그래프.py
65 lines (51 loc) · 1.69 KB
/
이분 그래프.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
"""
시작 시간: 2023-02-10 09:48 AM
소요 시간: 1시간 20분
풀이 방법: BFS에서 단계별로 색 다르게 칠해야될 때, 큐 두번 나눠서 사용하는 것 주의
"""
from collections import deque
from sys import stdin
input = stdin.readline
NO_COLOR=0
RED=1
BLACK=2
def get_another(color):
if color == RED:
return BLACK
return RED
def color_graph(vertex, color, graph, colors):
""" BFS로, vertex를 시작으로 color 번갈아가면서 색칠하기 """
queue = deque([vertex])
while queue:
next_queue = deque()
for _ in range(len(queue)):
vertex = queue.popleft()
if colors[vertex] == NO_COLOR:
colors[vertex] = color
for next_vertex in graph[vertex]:
next_queue.append(next_vertex)
elif colors[vertex] != color:
return False
color = get_another(color)
queue = next_queue
return True
def solution():
# 그래프 만들기
num_of_vertices, num_of_edges = map(int, input().rstrip().split())
graph = [ [] for _ in range(num_of_vertices + 1) ]
for _ in range(num_of_edges):
v1, v2 = map(int, input().rstrip().split())
graph[v1].append(v2)
graph[v2].append(v1)
colors = [NO_COLOR]*(num_of_vertices + 1)
# 색칠 안한 정점을 골라 그래프 색칠하기
color = BLACK
for i in range(1, num_of_vertices + 1):
vertex_color = colors[i]
if vertex_color != NO_COLOR:
continue
if not color_graph(i, color, graph, colors):
return "NO"
return "YES"
for _ in range(int(input().rstrip())):
print(solution())