그래프 이론 - 4. 이분 그래프

정의

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

 

판정

그래프의 정점들을 BFS 혹은 DFS로 탐색하면서 판단할 수 있다.

 

1. 방문하지 않은 정점을 찾는다.

2. 방문하지 않은 정점의 방문여부는 1로 체크한 후, 탐색을 시작한다.

1. 인접한 정점의 방문여부를 체크한다.
2. 인접 정점의 방문여부가 현재 정점의 방문여부와 같을 시, 해당 그래프는 이분그래프가 아니므로 시행을 종료한다.
3. 해당 정점을 방문하지 않았을 시, 현재 정점의 방문여부에 -1을 곱한 값으로 체크한다.

3. 만약 모든 정점의 순회가 중단되지 않았다면 해당 그래프는 이분그래프 이다.

 

코드

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

위 문제의 풀이이다.

import sys
input=sys.stdin.readline

def dfs(start, f):
 visited[start] = f
 queue = [start]
 while queue:
  curr = queue.pop()
  for neighbor in graph[curr]:
   if v[neighbor] == 0:
    queue += [neighbor]
    v[neighbor] = -v[curr]
   elif v[neighbor] == v[curr]: return
 return 1
 
for _ in range(int(input())):
 n,m = map(int,input().split())
 graph = [[] for _ in range(n+1)]
 visited = [0]*(n+1)
 
 for _ in range(m):
  start, end = map(int,input().split())
  graph[start] += [end]
  graph[end] += [start]
  
 i=f=1
 
 while i<=n:
  if visited[i]==0:
   d=dfs(i,f)
   if not d:print('NO'); f=0; break
  i+=1
  
 if f:print('YES')