1707 - 이분 그래프
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
코드
from collections import deque
def bfs(n, visited, check):
q = deque()
q.append(n)
visited[n] = True
check[n] = 1
while q:
x = q.popleft()
for nx in graph[x]:
if not visited[nx]:
q.append(nx)
check[nx] = check[x] * -1
visited[nx] = True
elif check[nx] == check[x]:
return False
return True
K = int(input())
for _ in range(K):
V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
for _ in range(E):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * (V+1)
check = [0] * (V+1)
flag = True
for i in range(1, len(graph)):
if not visited[i] and not bfs(i, visited, check):
flag = False
print("YES" if flag else "NO")한마디
문제에 있는 설명만으로는 이해가 잘 가지 않아 이분 그래프가 뭔지 찾아봤다. 이 문제는 쉽게 두 가지 색으로 인접한 정점은 다른 색으로 칠하면서 모든 정점을 칠할 수 있는지 물어보는 문제였다.
check 리스트를 만들어 시작 정점을 1로 설정해두었다. 다음 정점을 만날 때마다 -1을 곱했다. 이전 정점의 체크값과 현재 정점의 체크값이 같다면, 즉 같은 색으로 칠해야하는 경우기 때문에 false를 반환했다.
