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

1707 이분 그래프

• 문제
  • 1707번: 이분 그래프
• 해설

  • import sys
    
    sys.setrecursionlimit(99999)
    
    test_case_count = int(sys.stdin.readline().strip()[0])
    input_gen = (list(map(int, x.strip().split())) for x in sys.stdin.readlines())
    
    
    def trans(x):
        return -x
    
    
    def dfs(vertex, adj, chk, label_history, prev, res):
        chk[vertex] = True
    
        # labeling 한 적 없었으면 labeling
        if vertex not in label_history:
            label_history[vertex] = trans(prev)
    
        for neighbor in adj[vertex]:
            # Not bipartite인 경우 dfs 종료
            if neighbor in label_history and label_history[neighbor] == label_history[vertex]:
                res.append(1)
                break
            if not chk[neighbor]:
                dfs(neighbor, adj, chk, label_history, label_history[vertex], res)
    
    
    def check_bipartite(adj, chk):
        res = []
        first = True
        for vertex in adj:
            if first:
                dfs(vertex, adj, chk, {}, 1, res)
                first = False
            if chk[vertex] == False:
                dfs(vertex, adj, chk, {}, 1, res)
        if res:
            print('NO')
        else:
            print('YES')
    
    
    for case in range(test_case_count):
        vertex_count, edge_count = next(input_gen)
        chk = [False] * (vertex_count + 1)
        adj = {}
        for y in range(edge_count):
            vertex_1, vertex_2 = next(input_gen)
            if vertex_1 not in adj:
                adj[vertex_1] = [vertex_2]
            else:
                adj[vertex_1].append(vertex_2)
            if vertex_2 not in adj:
                adj[vertex_2] = [vertex_1]
            else:
                adj[vertex_2].append(vertex_1)
        check_bipartite(adj, chk)

• 포인트
  • DFS 설정