백준 11724 연결 요소의 개수 python

# 집합이 하나의 연결요소를 판단할때 사용
# 연결요소 자체를 하나의 집합으로 생각
# 간선이 들어 올때마다 유니온하면 각각의 연결요소를 하나의 집합으로 판단
# 연결 요소 == 집합
# 연결 요소 개수, 크기 DFS 안하고도 구할수가 있다아
# 그래프에서 연결요소 판별할때 사용
import sys; input = lambda: sys.stdin.readline().rstrip()

# 경로 압축
def find(x):
    if par[x] == x:
        return x
    par[x] = find(par[x])
    return par[x]


# union by rank
def union(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return
    if rnk[a] > rnk[b]:
        par[b] = a
    elif rnk[a] < rnk[b]:
        par[a] = b
    else:
        par[b] = a
        rnk[a] += 1

# 입력 정점 개수 n 간선의 개수 m
n,m = map(int, input().split())
# 루트 노드
par = [i for i in range(n+1)]
# 랭크 저장
rnk = [1 for _ in range(n+1)]

# 입력
for i in range(m):
# a, b 유니온
    a, b = map(int, input().split())
    union(a, b)

# 연결 요소 저장/ 중복된 루트를 제거 해주면 루트 요소 구할 수 있음
ans = set()

for i in range(1, n+1):
    ans.add(find(i))

# 개수 구하기
print(len(ans))