[SWEA] 5248. 그룹 나누기

find_set과 union을 사용하는 문제!

 

각 노드마다 부모를 가리키키는 리스트를 만들어주고

union연산을 통해 두 집합을 통합시킨다. 뒤에 오는 인자(y)가 부모노드가 된다.

여기서 find_set연산을 하는데, 노드X가 부모노드값과 같으면 노드 x값이 리턴이 되고 아니라면 다시 find_set함수로 들어가서 부모노드를 찾아 리턴시켜준다.

---

예시로

union(1,2)을 보면 parent =[0,1,2] 이다.

parent[find_set(2)] = find_set(1)

 

find_set(2)은

if 2 == parent[2]:

 return 2

 

대입하면

union(1,2):

parent[2] = find_set(1) 이 되고

 

find_set(1)은 리턴 1이므로 parent[2] = 1이 되어 

 

parent =[0,1,1]이 된다.

이런식으로 부모노드를 갱신해주어 부모노드의 개수를 출력해주면 되는 문제이다.

 

 

 

#find_set: x를 포함하는 집합을 찾는 연산
def find_set(x):
    if x == parent[x]:
        return x
    else:
        return find_set(parent[x])
# x와 y를 포함하는 두 집합을 통합하는 연산
def union(x,y):
    parent[find_set(y)] = find_set(x)

T = int(input())
for tc in range(1, T + 1):
    N, M = map(int, input().split())
    L = list(map(int,input().split()))
    #출석번호인덱스까지 parent리스트 만들어주기(0번은 사용안함)
    # 부모를 자기 자신으로 정의
    parent = [i for i in range(N + 1)]

    # 두개씩잘라서 한 쌍마다 union연산 해준다.
    for i in range(0,len(L),2):
        union(L[i],L[i+1])

    result = set()

    for i in range(1, N + 1):
        result.add(find_set(i))

    print("#{} {}".format(tc, len(result)))