[백준] 1707번: 이분 그래프

wikipedia image

문제

백준 - 1707번: 이분 그래프

분석

그래프에 대한 연결 정보가 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 문제이다.

썸네일 사진과 같이 연결되어 있는 노드는 서로 다른 그룹에 속해있는 그래프가 이분 그래프이다.
특정 점에서 dfs를 진행하면서 색을 번갈아가면서 표시를 해준다.(본인은 1, 2로 표시. 아직 방문을 안했으면 0)
만약 칠하려는 곳에 같은 색이 칠해져 있다면 더 이상 탐색할 필요없이 이분 그래프가 아닌 것으로 판명하면 된다.
주의할 점은 주어진 그래프가 모두 연결되어 있는지 알 수 없다. 따라서 모든 노드를 방문했는지 확인하면서 dfs를 진행한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

k = int(input())
def dfs(x, num): #num: 1, 2
    global isBi
    visited[x] = num
    for nx in graph[x]:
        if not visited[nx]:
            dfs(nx, 3-num)
        elif visited[nx] == visited[x]:
            isBi = False
            return
            
for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0]*(v+1)
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    isBi = True
    for i in range(1, v+1):
        if not visited[i]:
            dfs(i, 1)
            if not isBi:
                break
    print("YES" if isBi else "NO")             
    

끝으로..

이분 그래프에 대해 처음 배워보았다.