백준 20040 : 사이클 게임 (Python)

본문 링크

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


def Find(x):

    if disjoint[x]!=x:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a==b:
        return False
    else:
        if a>b:
            disjoint[a]=b
        else:
            disjoint[b]=a
        return True
N,M=map(int,input().split())

disjoint=[0]*N

for i in range(N):
    disjoint[i]=i

for i in range(M):
    a,b=map(int,input().split())

    if not Union(a,b):
        print(i+1)
        exit(0)
print(0)

📌 어떻게 접근할 것인가?

유니온 파인드를 사용해 풀었습니다. 문제에서 구하고자 하는 것은 그래프가 사이클이 생기는지 체크하는겁니다.

중요한것은 유니온 파인드로 두 노드를 합칠때 , 먼저 두 노드의 최상위 부모를 찾은 뒤에 그것이 같으면 합칠시 사이클이 생기므로 먼저 Find(a) 와 Find(b) 가 같은지 확인해줍니다.

같다면 바로 return False 를 해주고 그렇지 않으면 두 노드를 합쳐도 사이클이 생기지 않으므로
두 노드를 합쳐줍니다.