[Beakjoon] 20040. 사이클 게임

🔗 Problem Link

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

---

❔Thinking

• 방향이 없는 그래프에서 사이클이 형성되었는지 확인하고, 그 순간을 출력한다.
• 사이클이 없다면 0을 출력한다.

---

💻Solution

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

roots = [i for i in range(N)]

def find_root(x):
    if x != roots[x]:
        roots[x] = find_root(roots[x])
    return roots[x]

def union(a, b, roots):
    a = find_root(a)
    b = find_root(b)
    roots[max(a,b)] = min(a,b)

result = 0
for i in range(1, M+1):
    x, y = map(int, input().split())
    if find_root(x) != find_root(y):
        union(x,y,roots)
    elif result == 0:
        result = i        
print(result)

---

🗝️keypoint

1. 유니온 파인드를 활용해 사이클 여부를 확인하는 방법은, 새로운 두 노드의 루트가 같은지 확인하는 방법이다.