[알고리즘] 백준 1707 이분 그래프

문제

이분 그래프

 

접근

1. 테스트 케이스 안에서 노드의 개수와 간선의 개수를 받아야 하므로, 테스트 케이스 반복문 안에서 실행한다

2. 방문하는 곳이 그 전의 방문해서 나온 값이랑 같다면 노드끼리 간선에 의해 연결됨을 알 수 있으므로 break 해야한다

3. dfs함수에서 연결됨을 group으로 묶어서 판단하고 방문하지 않았으면 다른 그룹으로 판단하면 된다

 

풀이

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

k = int(input())


for _ in range(k):
    n, m = map(int, input().split())
    board = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    res = False

    for _ in range(m):
        a, b = map(int, input().split())
        board[a].append(b)
        board[b].append(a)

    def dfs(start, group):
        global res

        if res == True:
            return

        visited[start] = group  # 같은 그룹 선정

        for i in board[start]:
            if not visited[i]:
                dfs(i, -group)  # 다른 그룹
            elif visited[start] == visited[i]:
                res = True
                return

    for i in range(1, n+1):
        if not visited[i]:
            dfs(i, 1)
            if res:
                break

    if res == True:
        print("NO")
    else:
        print("YES")