서로 연결된 그룹 합치기

각 번호가 처음에는 자기 그룹을 대표해요

연결 집합과 재귀 방문을 배웠어요. 이번에는 연결이 추가될 때 두 그룹을 합쳐요. parent[node]는 그 번호가 따라갈 대표 번호예요. 처음에는 서로 연결되지 않아 parent =[0, 1, 2]처럼 각자 자신을 대표해요.

def find(node):
    if parent[node] == node:
        return node
    return find(parent[node])

find는 parent를 따라가다가 자기 자신을 가리키는 대표에서 멈춰요. parent =[0, 0, 1]이라면 find(2)는 2 → 1 → 0으로 이동해 0을 반환해요. 그림에서 저장된 parent와 최종 대표를 구분해요.

대표가 다를 때만 그룹을 합쳐요

두 번호 a·b를 연결하려면 first = find(a), second = find(b)로 현재 대표를 읽어요. 대표가 다르면 parent[second] = first로 한 대표가 다른 대표를 따르게 해요.

대표가 같으면 이미 연결된 그룹이라 바꾸지 않아요. 번호 a에 바로 b를 연결하면 기존 대표 관계를 끊거나 순환을 만들 수 있어요. 항상 그룹의 대표를 연결해요. 이 방법을 유니온파인드라고 해요. 대표가 작은 번호일 필요는 없고 같은 그룹이 하나의 대표에 도착하는 것이 중요해요.

남은 대표 수가 그룹 수예요

n = 3에서 0과 1을 합치면 parent =[0, 0, 2]이고 대표는 0·2 두 개예요. 이어 1과 2를 합치면 find(1)= 0, find(2)= 2라 parent[2]= 0이 돼요. 이제 대표는 0 하나예요.

모든 연결 뒤 parent[node] == node인 번호를 세어요. 분리된 번호도 자기 대표를 가진 한 그룹이에요. 같은 연결을 반복해도 새 그룹이 생기거나 사라지지 않아요.

직접 풀어봐요

번호 0~n −1의 장소에 양방향 연결을 추가한 뒤 서로 분리된 그룹 수를 출력해요. 중복 연결과 자기 연결도 허용해요.

첫 줄 n(120), 둘째 줄 m(0100), 이후 연결마다 a 한 줄, b 한 줄(각 0~n −1)이에요. 출력은 그룹 수예요.

예시 1: n = 4, 연결[(0, 1),(2, 3)] → 2예요. 예시 2: n = 3, 연결[(0, 1),(1, 2)] → 1예요.

4
2
0
1
2
3

2

3
2
0
1
1
2

1