[백준] 20040 사이클 게임

문제

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

20040번: 사이클 게임

 

풀이

- 문제에서 '  사이클을 완성하는 순간 게임이 종료 ' 라는 말을 보고 우리가 기본적으로 아는 서로소 집합 ( union-find ) 이라고 생각했다

- ' m 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력한다. ' 을 볼 수 있는데, 이는 m번을 다돌았는데 다같이 find가 다를수있다는 말이다

- 이미 정답이 나왔으면 더이상 실행할 필요가 없다. ( 하지만 나는 데이터를 전부 받고 나서 진행했는데 성공했다 )

 

코드

# 골드4 - 사이클 게임
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

parent = [i for i in range(n)]


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


def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


cnt = 0
data = []
for i in range(m):
    a, b = map(int, input().split())
    data.append([a, b])

for i in range(m):
    if find(data[i][0]) != find(data[i][1]):
        union(data[i][0], data[i][1])
        cnt += 1
    else:
        break

if cnt == m:
    print(0)
else:
    print(cnt+1)