Problem Solving/Union-Find & Minimum Spanning Tree

[유니온-파인드] 백준 20040번: 사이클 게임 / 골드 4

by ggyongi 2021. 8. 19.

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

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한

www.acmicpc.net

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parents = [i for i in range(n)]

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        return find(parent, parent[x])

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a > b:
        parent[a] = b
    else:
        parent[b] = a

for i in range(m):
    a, b = map(int, input().split())
    if find(parents, a) != find(parents, b):
        union(parents, a, b)
    else:
        print(i+1)
        quit()

print(0)

union-find를 이용하면 사이클 여부를 쉽게 확인할 수 있다.