[ 4195 ] [ Union-find ] 친구 네트워크

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

---

풀이 과정

1. 이전에 나타나지 않은 인원의 경우 딕셔너리에 넣어준다.
   • 딕셔너리에 넣어주면서 parent 설정, 인원수 1명(자기 자신) 설정
2. 입력받은 두명의 그룹을 합친다.
   • 이 때, 두명이 속한 그룹의 인원수도 같이 합쳐주어야 함.
   • 인원수를 따로 구하려고 하면 시간 초과가 나온다.
3. 매 과정마다 그룹 내의 인원수를 출력해준다.

• 처음에는 인원수를 따로 for문으로 구하려고 했는데 시간초과가 나옴..
• 처음 시간초과가 났을 때는 차라리 set을 사용해서 구현하는 것이 더 편할거 같았으나..
  Union-Find로 통과받아보고 싶어서 매달림,,

---

소스 코드

import sys
input = sys.stdin.readline

total_case = int(input().rstrip())

def find(parent, group, a):
    if parent[a] != a:
        parent[a] = find(parent, group, parent[a])
        group[a] = group[parent[a]]
    return parent[a]

def union(parent, group, a, b):
    p1 = find(parent, group, a)
    p2 = find(parent, group, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

for i in range(total_case):
    F = int(input().rstrip())
    member = dict()
    count = 0
    parent = [-1] * 200001
    group = [0] * 200001
    for _ in range(F):
        person1, person2 = input().rstrip().split()

        # 새로운 멤버 추가
        if member.get(person1) == None:
            parent[count] = count
            member[person1] = count
            group[count] = 1
            count += 1
        if member.get(person2) == None:
            parent[count] = count
            member[person2] = count
            group[count] = 1
            count += 1

        # 두 그룹 합침
        par1 = find(parent, group, member[person1])
        par2 = find(parent, group, member[person2])
        if par1 != par2:
            union(parent, group, par1, par2)
            # 그룹 인원수 합침
            temp = group[par1] + group[par2]
            group[par1] = temp
            group[par2] = temp

        # 위 과정에서는 부모의 그룹 인원수만 바뀌므로   
        # find 한번 더 호출해서 자식들의 그룹 멤버 수가 부모의 그룹 인원수가 되도록 조정
        find(parent, group, member[person1])
        find(parent, group, member[person2])

        group_count = group[member[person1]]
        print(group_count)