[python] 백준 20040 : 사이클 게임

문제 링크
https://www.acmicpc.net/problem/20040

접근

사이클이 생기는지 파악하는 문제다. 최적화된 Union-Find 알고리즘을 이용하여 풀면 되겠다고 생각했다.

최적화된 Union-Find 알고리즘

알고리즘에 대한 설명은 도시 분할 계획 풀이와 동일하므로 링크로 대체한다.
최적화된 Union-Find 알고리즘 설명

def union(v1, v2):
    r1 = find(v1)
    r2 = find(v2)

    if rank[r1] > rank[r2]:
        root[r2] = r1
    elif rank[r1] < rank[r2]:
        root[r1] = r2
    else:
        root[r2] = r1
        rank[r1] += 1


def find(v):
    if v == root[v]:
        return v
    root[v] = find(root[v])
    return root[v]


n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [0 for _ in range(n)]

풀이

알고리즘은 간단하다.
서로 다른 두 점이 주어질 때마다 그 두 점을 union 함수를 이용하여 합치고, 만일 그 두 점의 root가 같으면 사이클이 생긴 것이므로 탐색을 종료한다.

def solve():
    for i in range(m):
        a, b = map(int, input().split())
        if find(a) == find(b):
            print(i + 1)
            return
        union(a, b)
    print(0)
    return

정답 코드

import sys

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()


def union(v1, v2):
    r1 = find(v1)
    r2 = find(v2)

    if rank[r1] > rank[r2]:
        root[r2] = r1
    elif rank[r1] < rank[r2]:
        root[r1] = r2
    else:
        root[r2] = r1
        rank[r1] += 1


def find(v):
    if v == root[v]:
        return v
    root[v] = find(root[v])
    return root[v]


n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [0 for _ in range(n)]
conn = [0 for _ in range(m)]


def solve():
    for i in range(m):
        a, b = map(int, input().split())
        if find(a) == find(b):
            print(i + 1)
            return
        union(a, b)
    print(0)
    return

solve()