[백준 20040] 사이클 게임

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

20040번: 사이클 게임

---

접근

사이클이 완성되기 위해서는 최소 세 개의 점이 연결되어야 한다. 이를 유니온 파인드 알고리즘을 활용하여 해결할 수 있다. 입력되는 두 개의 점이 있을 때 한 쪽 점을 다른 쪽에 속한 집합으로 합친다. 이후에 두 개의 점을 입력받았을 때 루트 노드가 같다면 사이클이 완성되었다고 판단할 수 있다.

 

구현

- 아래와 같이 union와 find 연산을 함수로 만든다.

def find(a):
    if p[a] == a:
        return a
    else:
        b = find(p[a])
        return b

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        p[b] = a

- M번 동안 두 개의 점을 입력받는다.

- 이때 a가 b보다 클 때는 두 개의 점을 교환한다.

- 만약 두 개의 점의 루트 노드가 같을 때는 입력받는 것을 종료하고 answer에 m+1로 저장 후에 종료한다.

- 다르다면 두 개의 점을 union 연산을 통해 합친다.

answer = 0
for m in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a

    if find(a) == find(b):
        answer = m + 1
        break
    else:
        union(a, b)

---

전체 코드

import sys
input = sys.stdin.readline

def find(a):
    if p[a] == a:
        return a
    else:
        b = find(p[a])
        return b

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        p[b] = a


N, M = map(int, input().split())
p = [n for n in range(N)]

answer = 0
for m in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a

    if find(a) == find(b):
        answer = m + 1
        break
    else:
        union(a, b)

print(answer)