[백준/파이썬] 1707번 이분 그래프

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

1707번: 이분 그래프

이분 그래프인지 아닌지를 판단하는 문제이다

정점 하나하나씩 bfs 탐색을 진행해주는데, 주의해야 할 점은 그룹을 지어야 한다는 것이다!

(왜 bfs를 한번에 돌리지 않고, 정점 하나씩 해주냐면 입력이 어떻게 들어올 지 모르기 때문이다. 비연결 그래프가 존재하는 경우, 시작점과 연결되지 않은 곳은 탐색할 수 없기 때문에 모든 정점에 대해 탐색해주는 것이다)

트리를 하나 떠올려 보자. level 0 노드는 level1 노드와 인접해있지만, 각 level 안에 있는 노드들끼리는 인접해있지 않다.

 

때문에 level 0을 하나의 그룹으로 묶고, level 1을 하나의 그룹으로 묶을 수 있다면 해당 그래프는 이분 그래프이다

이를 1과 -1을 이용해 구별지어 주자.

근데 만약, 나와 연결된 노드가 나와 level이 같다면 (예를 들어 싸이클을 이루는 경우,,) 주어진 그래프는 이분 그래프가 될 수 없다

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def bfs():
  q = deque()
  level = 1

  for i in range(1,v+1):
    if visited[i]==0:
      q.append(i)
      visited[i] = level
      
      while q:
        now = q.popleft()
        
        for next in graph[now]:
          if visited[next]==0:
            q.append(next)
            visited[next] = -1 * visited[now]
          elif visited[next]==visited[now]: #
            return False
          
  return True

if __name__ == "__main__":
  t = int(input())
  for _ in range(t):
    v,e = map(int,input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)
    
    for _ in range(e):
      x,y = map(int,input().split())
      graph[x].append(y)
      graph[y].append(x)
      
    print('YES' if bfs() else 'NO')