[SWEA] 5248: 그룹 나누기

# 문제 설명

수업에서 같은 조에 참여하고 싶은 2명끼리 출석번호를 제출한다.

한 조의 인원 수 제한을 두지 않았기 때문에, 한 사람이 여러 장의 종이를 제출하거나 여러 사람이 한 사람을 지목한 경우 하나의 팀이 된다.

 

출석번호는 1~n번까지가 있고, m장의 신청서가 제출되었을 때,

전체 몇 개의 조가 만들어지는지 구하라.

 

# 입출력 예시

입력	출력
3 5 2 1 2 3 4 5 3 1 2 2 3 4 5 7 4 2 3 4 5 4 6 7 4	#1 3 #2 2 #3 3

 

# 코드 풀이

def union(parent, x, y):
    a = find(parent, x)
    b = find(parent, y)
    if a > b:
        parent[a-1] = b
    else:
        parent[b-1] = a

def find(parent, x):
    if parent[x-1] != x:
        parent[x-1] = find(parent, parent[x])
    return parent[x-1]

def get_group_no(n, parent, pair):
    for x, y in pair:
        union(parent, x, y)
    return len(set([find(parent, i) for i in range(1, n+1)]))

T = int(input())
for test_case in range(1, T+1):
    n, m = map(int, input().split(' '))
    parent = [i for i in range(1, n+1)]
    rest = list(map(int, input().split(' ')))
    pair = []
    while len(rest) != 0:
        x, y, *rest = rest
        pair.append([x, y])
    print('#{} {}'.format(test_case, get_group_no(n, parent, pair)))

 

# 핵심 포인트

- 서로 겹치는 부분이 존재하지 않는 상호배타적인 그룹을 형성하기 때문에, UnionFind 알고리즘을 사용한다.

- 출석번호가 1~n번까지 존재하므로, 그에 맞춰서 parent나 인덱스를 조정한다.