[SWEA] 7465_창용 마을 무리의 개수

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU 

SW Expert Academy

 

💡 풀이법

1. 관계들을 입력받으면서 두 노드들을 union  시킨다.

2. 모든 관계들을 union하고 나면 그룹이 만들어지게 된다.

3. 각 노드들을 돌면서 노드들의 루트들을 찾으면 그 루트들의 개수가 그룹의 무리의 개수가 된다.

 

def find_set(x):
    if x == parents[x]:
        return x
    return find_set(parents[x])

def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    if root_x != root_y:
        parents[root_y] = root_x
    return True

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())

    nodes = [i for i in range(1, N + 1)]
    parents = [i for i in range(N + 1)]

    for _ in range(M):
        n1, n2 = map(int, input().split())
        union(n1, n2)

    root = set()
    for node in nodes:
        root.add(find_set(node))

    print('#{} {}'.format(tc, len(root)))