백준 20040번 : 사이클 게임 in Python

20040번: 사이클 게임

 

www.acmicpc.net

이 문제는 그래프에 간선을 차례대로 그릴 때 언제 사이클이 처음으로 생기는지를 묻는 문제이다. 

만약 모든 간선이 동시에 주어진 상태에서 사이클 유무를 물었다면 그래프를 그리고 그래프 탐색을 통해 사이클 유무를 따져도 되지만, 이 문제는 간선을 하나씩 그리면서 사이클 유무를 따져야 하기 때문에 만약 단순히 그래프 탐색을 통해 사이클 유무를 따진다면 m번의 그래프 탐색을 반복해야 하고, 이는 매우 비효율적이다.

그래서 이는 그래프 탐색이 아닌 분리 집합을 이용해 해결한다. 만약 어떤 간선이 주어졌을 때 그 간선 위의 두 점이 속한 집합이 같은 경우 그 간선 없이도 두 점이 서로 연결되어 있음을 의미하는데, 만약 그 간선을 추가한다면 두 점 사이의 경로가 두 개가 발생해 이를 연결하면 사이클이 만들어진다. 그러므로 매번 간선이 주어질 때마다 그 간선 위의 두 점이 속한 집합이 같은지만 검사하면 사이클이 생겼는지를 바로 알 수 있다.

이를 코드로 구현하면 다음과 같다.

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

def find(u):
    if parent[u] == u: return u
    parent[u] = find(parent[u])
    return parent[u]
def union(u, v):
    root_u = find(u)
    root_v = find(v)
    parent[root_u] = root_v
n, m = map(int, input().split())
parent = [i for i in range(n+1)]
# 언제 사이클이 생기는지를 알려주는 변수
cycle_completed = 0
for i in range(m):
    a, b = map(int, input().split())
    # 간선이 추가됨으로 인해 사이클이 발생하는 경우
    if find(a) == find(b):
        cycle_completed = i+1
        break
    else:
        union(a, b)
# 사이클이 생기지 않는 경우 cycle_completed가 수정되지 않으므로 초기값인 0이 출력된다.
print(cycle_completed)