친구 네트워크

• 그냥 Disjoint Set 을 이용해서 구현하면 끝나는 간단한 문제.
• 다만 번거로운 것은 입력값이 문자열 타입이라는 것. teflib의 DisjointSet을 사용하기 위해서는 문자열 형식의 이름들을 [0,n)까지의 자연수로 변환해서 넣어줘야 한다. 변환하는 것은 변환 테이블을 defaultdict(count().__next__) 트릭을 써서 만들면 간단하게 처리할수 있다.
• m개의 친구관계에 대해서 O(α(n))의 union 작업과, O(1)의 크기 갱신 작업이 필요하다. 총 시간 복잡도는 O(m*α(n)). 이때, n은 친구의 수인데 따로 제한이 주어져있지 않으므로 최대 2*m명까지 가능하다고 봐야 한다. 그렇다면 총 시간 복잡도는 O(m*α(m))으로 쓸수있다.

"""Solution code for "BOJ 4195. 친구 네트워크".

- Problem link: https://www.acmicpc.net/problem/4195
- Solution link: http://www.teferi.net/ps/problems/boj/4195

Tags: [DisjointSet]
"""

import collections
import itertools
import sys
from teflib import disjointset


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        F = int(sys.stdin.readline())
        id_by_name = collections.defaultdict(itertools.count().__next__)
        dsu = disjointset.DisjointSet(F * 2)
        for _ in range(F):
            name1, name2 = sys.stdin.readline().split()
            merged_set = dsu.union(id_by_name[name1], id_by_name[name2])
            print(dsu.size(merged_set))


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet