[백준] Union & Find - 사이클 게임

지난번 유니온파인드 개념에 대해 알아보았다.

 

각 노드들을 병합시켜 가리키고 있는 root-node로 업데이트를 진행시키는 방법이었다.

그 후 병합된 정보를 바탕으로 find을 찾아 같은 그래프에 속해있는지, 사이클이 있는지 살펴 볼 수 있다고 하였다.

 

그럼 적용가능한 문제를 하나 풀어보고자 한다.

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

 

'백준'사이트에 있는 '사이클 게임' 문제이다.

문제를 간단하게 정리해보면, 노드간 간선을 하나씩 그리는 게임을 하게 되는데, 진행하다보면 어느순간에 cycle이 생기는 순간이 생길것이다. 이걸 판단해 줄 수 있는 프로그램을 만들어 달라는 것이다.

 

정확히 유니온 파인드 알고리즘만 알고 있으면 풀 수 있는 문제다.

 

이 문제의 핵심은 Find에 존재한다. 유니온을 진행하다 간선을 연결하기 위해 A,B의 노드의 Root-node가 이미 둘이 같다면, 이미 하나의 그래프로써 존재하고, A,B 간선을 그리게 되면 사이클이 생긴다는 소리다! 

 

즉, A,B 두 노드의 Root-Node가 같은데 추가로 A,B 간선을 만들면 사이클이 생성되니 이때를 판단해주면 되는 문제였다.

 

import sys

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

N , m = map(int,input().split(" "))

def getparent(parent_ , number):
    if parent_[number] == number:
        return number
    parent_[number ] = getparent(parent_, parent_[number])
    return parent_[number ]

def union_parent(parent_ ,a ,b ):
    a = getparent(parent_ , a )
    b = getparent(parent_ , b )
    
    if a < b : 
        parent_[b] = a 
    else:
        parent_[a] = b
        
def find_cycle(parent_ , a, b):
    a = getparent(parent_ , a )
    b = getparent(parent_ , b )
    
    if a == b:
        return 1 
    else:
        return 0


number_ = [x for x in range(N + 1)]
parent_ = [x for x in range(N + 1 )]

count = 0
result = [] 
for _ in range(m):
    n1, n2 = map(int,input().split(" "))
    count +=1
    
    # union
    flag = find_cycle(parent_,n1,n2)
    union_parent(parent_ , n1, n2 )

    if flag :
        result.append(count)
if len(result) == 0:
    print(0)
else:
    print(result[0])