[백준] 20040번 : Cycle Game

해당 문제는 서로소 집합 문제로 사이클이 생겼는지 안생겼는지에대한 판별을 하는 문제이다.

<aside> 💡 여기서 실수한건 union 함수에서 각각의 원래의 부모의 값을 업데이트 해주어야 하는데, 자기자신의 부모값을 업데이트 하는 실수를 하였다. 또한 M 번째에서 사이클이 발생할 경우도 예외 처리를 해주어야한다.

</aside>

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
parent = [i for i in range(N)]

def find(v1):
    if parent[v1] != v1:
        parent[v1] = find(parent[v1])
        return parent[v1]
    else:
        return v1

def union(v1, v2):
    p1 = find(v1)
    p2 = find(v2)

    if p1 > p2:
        parent[p1] = p2
    else:
        parent[p2] = p1

cnt = 0
iscycle = False
for _ in range(M):
    v1, v2 = map(int, input().split())
    p1 = find(v1)
    p2 = find(v2)
    cnt += 1
    if p1 == p2: # Cycle Made
        iscycle = True
        break
    else:
        union(v1, v2)

if cnt == M and not iscycle:
    print(0)
else:
    print(cnt)