[백준]1707 이분그래프

1. 풀이

이분그래프를 확인하는 방법은 다음과 같다.

(1) 2개의 색깔을 가지고 dfs를 통해 인접한 노드에 다른 색깔을 칠하며 전체를 다 칠하기.

(2) 2중 포문을 통해 인접한 노드에 다른색이 칠해져 있는지 확인.

-> 다른색이 칠해져 있으면 이분그래프 될 수 없음.

(3) 이분그래프

 

2. 소스코드

import sys

sys.setrecursionlimit(10 ** 7)

k = int(input())
turn = [1, 0]


def cheak():
    for v in range(1, V + 1):
        nowColor = colorV[v]
        for conNode in graph[v]:
            if colorV[conNode] == nowColor:
                print("NO")
                return
    print("YES")


def dfs(node):
    color = colorV[node]
    for conNode in graph[node]:
        if colorV[conNode] == -1:
            colorV[conNode] = turn[color]
            dfs(conNode)


for t in range(k):
    V, E = map(int, sys.stdin.readline().rstrip().split())
    graph = {}
    for i in range(1, V + 1):
        graph[i] = []
    a=0
    for i in range(E):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)
    # print(graph)
    # 색 칠하기
    colorV = [-1 for i in range(V + 1)]
    for i in range(1,V+1):
        if colorV[i]==-1:
            colorV[i] = 1
            dfs(i)
    # print(colorV)
    # 확인하기
    cheak()