서로소 집합(disjoint set) 연습

서로소 집합 관련 문제

해결 방법 : 각 사람의 친구관계를 dict으로 설정하여 Q가 입력되면 해당하는 value(친구의 수)를 출력하고 M이 입력되면 각 value를 합친다.

 

문제점 : 이 문제에서 disjoint set이 어디에 해당하는지 모르겠다.

 

코드

n, m = map(int,input().split())

 

input_info = []

 

human_relations = dict()

 

for i in range(1,n+1):

    human_relations[i] = 1

 

for i in range(m):

    a = input().split()

    if a[0] == 'Q':

        a[1] = int(a[1])

        print(human_relations[a[1]])

    elif a[0] == 'M':

        a[1] = int(a[1])

        a[2] = int(a[2])

        num_friend_1 = human_relations[a[1]]

        num_friend_2 = human_relations[a[2]]

        human_relations[a[1]] = num_friend_1 + num_friend_2

        human_relations[a[2]] = human_relations[a[1]]