[SWEA] 5248_그룹 나누기

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. find_set함수는 그 노드가 속해있는 집단의 대표자를 찾는 함수이다,

2. union 함수는 두 노드를 합치는 함수이다.

3. 간선의 정보를 다 받아서 간선으로 이어져 있는 노드들은 union 함수를 적용시켜준다.

4. 모든 노드들을 돌면서 각 노드들이 속해있는 집단의 대표자의 개수를 구하면 몇개의 조가 만들어져있는지 알 수 있다.

 

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())
    union_list = list(map(int, input().split()))

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

    for i in range(0, M*2, 2):
        union(union_list[i], union_list[i+1])

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

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