백준 20040번: 사이클 게임 (Union, find)

문제링크:20040번: 사이클 게임 (acmicpc.net)

20040번: 사이클 게임

이 문제는 먼저 정점의 개수 N이 주어지고 이후로 두 정점을 연결하는 간선이 계속해서 주어지는데, 이 때 정점간의 사이클이 발생하는 것을 판단하는 문제이다. 정점의 개수가 500,000개이고 주어지는 간선이 1,000,000개이므로 노드에서 DFS로 사이클을 판단하면 시간 초과가 발생한다. 여기서는 분리 집합을 사용해야 하는데, 분리 집합이란 한 정점이 다른 정점에 연결되었을 때에 한 정점을 부모 노드로 삼는 것이다. 만약 다른 정점이 간선으로 연결될 때마다 부모 노드의 하위 노드로 연결해주면, 연결된 트리의 노드들의 최고 부모 노드 탐색 시 항상 같게 나오게 된다. 그렇게 해서 만약 새로운 간선이 입력될 때마다 두 정점의 최고 부모 노드를 확인하고 최고 부모 노드가 다르면 한 트리를 다른 트리에 연결해주고, 만약 최고 부모 노드가 같다면 같은 트리 내의 정점을 연결한 것이 되므로 사이클이 발생한 것이다.

import sys

sys.setrecursionlimit(999999)

n,m=map(int,sys.stdin.readline().rstrip().split())

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

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

def union(x,y):
    x=find_root(x)
    y=find_root(y)
    if x!=y:
        parent[x]=y

cnt=0
for i in range(m):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    if cnt==0:
        if find_root(a)==find_root(b):
            cnt=i+1
    union(a,b)

print(cnt)

분리 집합을 구현하는 법은 먼저 초기에 각 정점들은 하나도 연결되지 않았으므로 각자의 부모 노드는 자기 자신이다. parent 리스트는 각 인덱스(정점)의 상위 노드를 저장한다고 생각하면 된다. 만약 입력이, a,b로 주어지게 된다면 a와 b의 부모 노드를 find_root()를 통해 탐색한다.

 

find_root()함수는 탐색하는 노드의 상위 노드가 없을때까지 (최고 부모 노드를 만날때까지) 탐색한다. 최고 부모 노드는 parent[x]가 자기 자신인 노드이다. 중간에 parent[x]=find_root(parent[x])는 parent 리스트의 상위 노드를 최고 부모 노드로 업데이트 해주는 역할을 한다. 만약 1->2->3 순으로 1이 최고 부모 노드라고 가정하자. 초기에는 parent[3]=2 이고 parent[2]=1이므로 3의 최고 부모 노드가 1인것을 찾았다면, 나중에 정점 3의 최고 부모 노드를 찾을 일이 다시 생겼을때 parent[3]=1 로 업데이트를 해준다면 다른 노드를 거치지 않고 바로 최고 부모 노드를 찾을 수 있게 해준다.

 

다음으로 union()함수는 두 정점(x,y)의 최고 부모 노드(find_root(x), find_root(y))가 만약 다르다면 최고 부모 노드 하나를 다른 최고 부모 노드 하위에 위치시켜 두 트리가 한 트리가 될 수 있도록 한다. 위 함수에선 parent[x]=y 이므로 x의 최고 부모 노드가 였던 트리가 y의 최고 부모 밑으로 들어가게 되는 것이다. 최고 부모 노드가 y밑으로 들어갔으므로 당연히 x의 트리 아래의 노드들도 y밑으로 들어가게 되어 모두 y의 최고부모를 부모 노드로 갖는 하나의 트리가 된다.