[BOJ/python]1707번 이분 그래프

백준 1707번 이분 그래프 파이썬

문제 링크 - https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

두 개의 그룹으로 노드를 나누고, 하나의 그룹의 노드끼리 연결되지 않도록 해야 한다. 문제를 보자마자 간단한 분리 집합 문제라고 생각했다. 하나의 노드를 기준으로 설정하고, 연결된 노드들을 모두 union 한다. 이 때 같은 부모를 가지는 집합에서 연결된 노드가 있다면 ‘NO’를 출력한다. 하지만 굳이 union을 할 필요 없이 BFS만으로도 간단히 풀 수 있다.

1. 풀이

• 방문하지 않은 모든 정점을 시작점으로 BFS를 실행한다.
• 방문 표시를 1,-1로 나누어 그룹을 구분한다.
• 현재 노드를 방문 처리하고, 연결된 노드들은 다른 숫자로 방문 처리한다.
• 만약 다음 노드가 이미 방문 처리 되었고, 현재 노드와 같은 숫자로 표시되었다면 ‘NO’를 반환한다.

2. 코드

from collections import deque
import sys
input = sys.stdin.readline

def BFS(G):
    visited = [0 for _ in range(V+1)]
    for i in range(1,V+1):
        if visited[i]==0:
            q = deque([i])
            visited[i]=1
            while q:  
                node = q.popleft()
                
                nodeTeam = visited[node]
                nextTeam = nodeTeam*-1
                for next in G[node]:
                    if visited[next]==0:
                        visited[next] = nextTeam
                        q.append(next)
                                
                    elif visited[next] == nodeTeam:
                        return 'NO'
    return 'YES'

T = int(input())
for _ in range(T):
    answer='YES'
    
    V,E = map(int,input().split())
    # graph = [[0 for _ in range(V+1)] for _ in range(V+1)]
    G = [ [] for _ in range(V+1)]

    for i in range(E):
        u,v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
        
    answer = BFS(G)
    print(answer)