[bj1717] 집합의 표현

문제

• 백준 URL: 집합의 표현
• 난이도 골드 5

풀이

유니온 파인드를 사용하여 풀이했다.
finder() 함수를 통해 노드들이 입력되었을 때 해당 노드들의 부모가 같도록 묶어주고, 부모 노드를 비교하였을 때 값이 같은 경우 같은 집합에 속하는 것으로 볼 수 있다.

n,m = map(int,input().split())
li = [i for i in range(n+1)]
def finder(a):
    if a!=li[a]:
        li[a] = finder(li[a])
    return li[a]
for _ in range(m):
    n,a,b = map(int,input().split())
    if n: print(['NO','YES'][finder(a)==finder(b)])
    else:
        l = finder(a)
        r = finder(b)
        li[r] = l

기타

문제 조건에서 m이 최대 100,000이다.
입력받는 경우가 적으면 상관 없지만 이 경우 최대 100,000번이나 입력받는 경우가 생기므로, sys.stdin.readline()을 사용하면 시간을 크게 단축시킬 수 있다.

import sys
n,m = map(int,input().split())
li = [i for i in range(n+1)]
def f(a):
    if a!=li[a]: li[a] = f(li[a])
    return li[a]
for _ in range(m):
    n,a,b = map(int, sys.stdin.readline().split())
    if n: print(['NO','YES'][f(a)==f(b)])
    else:
        l,r = f(a),f(b)
        li[r] = l