[BOJ] 1707 / 이분 그래프 / Python 파이썬

[BOJ] 1707 / 이분 그래프 / Python 파이썬

[BOJ] 1707 / 이분 그래프 / Python 파이썬

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

풀이

이분 그래프 (Bipartite Graph) 를 판별하는 문제이다.

 

그래프를 탐색하면서 node 에 -1 을 곱해주는 것으로 이분 그래프를 검사하였다.

 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())

    nums = list(map(int, input().split()))
    nums = [0] + nums

    cnt = 0

    for f in range(1, N+1):
        if nums[f] < 0:
            continue
        cnt += 1
        t = nums[f]
        nums[f] = -1
        while True:
            if t < 0:
                break
            f = t
            t = nums[f]
            nums[f] = -1
    print(cnt)

 

※ 이분 그래프에 대해 알고 있었다면 더 쉽게 풀수 있었을 것이다.