[백준] 이분 그래프 DFS 다시 풀기

import sys
sys.setrecursionlimit(10**6)
    
def dfs(V, color):
    colors[V] = color
    for node in graph[V]:
     	#colors는 0, -1, 1
        if colors[node] == 0: #방문X
            result = dfs(node, -1 * color)
            if not result:
                return False
        elif colors[V] == colors[node]:
            return False
    return True
        


input = sys.stdin.readline
K = int(input())

for i in range(K):
    V, E = map(int, input().split())
    graph = [[] for i in range(V+1)]
    for i in range(E):
        u, v= map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    colors = [0] * (V+1)
    for i in range(1, V+1):
        if not colors[i]:
            result = dfs(i,1)
        if not result:
            break
    print("YES" if result else "NO")

 

for문을 통해 파라미터로 받은 V와 연결된 노드들을 하나씩 확인한다.

그 노드가 colors 배열에서 0이면 방문하지 않은 노드로 dfs(1, -1 * colors)로 V와 다른 색을 칠해준다.

그 노드가 만약 colors배열에서 0이 아니라 V와 같은 색이라면 이분 그래프가 아니므로 False를 리턴한다.

그러면 앞의 if문에서 실행한 dfs의 결과를 result로 받게 되는데 result가 False이면 False를 리턴함으로써 함수 실행을 끝낸다.

이외의 경우는 True로 리턴한다.