백준 1717번 - 집합의 표현

범위

1 <= n <= 1 000 000
1 <= m <= 1 00 000

풀이과정

기본 Union-Find

실패 시간초과
기본적인 Union-Find 을 사용해봤다. 결과는 바로 실패

분석

연산 수는 최대 100000번.
최적화되지 않은 경우 최악의 경우 O(n)의 시간복잡도를 가진다.
=> 100000 X 100000 = 10000000000 로 시간제한을 넘게된다.

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

def find(x):
    while x != parent[x]:
        x = parent[x]
    return x

def union(x, y):
    parent[find(y)] = parent[find(x)]

for _ in range(m):
    t, a, b = list(map(int, input().split()))
    if t == 0:
        union(a, b)
    if t == 1:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")

Union by rank

실패 시간초과
개선된 방법인 Union by rank 를 사용해서 코드를 작성했다.

n, m = map(int, input().split())

parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)

def find(x):
    while x != parent[x]:
        x = parent[x]
    return x

def union(x, y):
    a, b = find(x), find(y)
    if a != b:
        if rank[a] < rank[b]:
            parent[a] = b
        elif rank[a] > rank[b]:
            parent[b] = a
        else:
            parent[b] = a
            rank[a] += 1

for _ in range(m):
    t, a, b = list(map(int, input().split()))
    if t == 0:
        union(a, b)
    if t == 1:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")

시간초과

시간 초과가 발생했다.
시간복잡도 100000 x log 100000 로 유사하여 시간 초과가 발생하지 않을 줄 알았는데 발생했다.

Union by rank + stdin

성공 340ms
input을 sys.stdin.readline() 으로 바꾸니까 너무 간단하게 성공했따.
그것도 엄청나게 빠른 속도로...
꼭 stdin을 사용해야겠다.
추가로 정리한 input vs stdin

path compression

성공 484ms

import sys

n, m = map(int, input().split())

parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)


def find(x):
    # while x != parent[x]:
    #     x = parent[x]
    # return x
    y = x
    while y != parent[y]:
        y = parent[y]
    parent[x] = y
    return y


def union(x, y):
    parent[find(y)] = parent[find(x)]


for _ in range(m):
    t, a, b = list(map(int, sys.stdin.readline().split()))
    if t == 0:
        union(a, b)
    if t == 1:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")

경로 압축을 사용한 union-find로도 시간 초과가 발생하지는 않지만, union by rank에 비해 속도가 조금 더 느렸다.
find 연산이 이루어지기 전에는 경로압축이 되지 않아서 그런것 같다.(뇌피셜)

Union-Find