백준 4195 친구 네트워크

일단 인덱스에러 때문에 한참 고생했는데, 관계 F가 10만개이니 가능한 친구 수는 10만개 이상일 수 있는데, 친구를 담는 리스트를 10만개로 설정해놓으니 인덱스 에러가 뜨는 것이었다 (종현이 감사 ^^)

이 에러를 해결해도 시간초과가 발생했는데, 결과적으로 복잡도가 N^2이 되면 안되는 것이었다.

이 문제에서 주안점으로 본 사항은
1. 교재의 내용에 따르면 어떤 노드를 union했을 때 children의 parent는 갱신되지 않는다는 점.

2. 집합의 크기를 구해야하기 때문에 일일히 부모가 무엇인지 계산해야한다는 점
   

이다. 이 두가지 사항에서 N^2이 발생하기 때문에 이것들을 for문 없이 구현하는 것이 핵심이라고 파악했다.

이것들을 for문 없이 구현하기 위해 딕셔너리를 적극적으로 활용했다.
총 3개의 딕셔너리를 사용했는데
1. 부모의 이름을 저장하는 딕셔너리 (변수명: parents)
2. 자식이 무엇이 있는지 리스트로 저장하는 딕셔너리 (변수명: list_of_child)
3. 집합의 크기를 저장하는 딕셔너리 (변수명: roots)
로 나누었다.

1을 이용하여 find_children을 따로 할 필요가 없어졌고, find_children에서 각 자식들을 찾아 부모를 바꿔줘야했기 때문에 이 부분에서 for문을 사용해 N^2이 되었다. 하지만 2를 이용하여 이 부분도 for문없이 가능해졌다.
마지막으로 3을 이용해 집합의 크기를 for문 없이 구할 수 있게 되었다.

코드는 다음과 같다.

import sys
from collections import defaultdict

N = int(input())
for _ in range(N):
    F = int(input())
    roots = {}
    parents = {}
    list_of_child = defaultdict(list)
    
    for p in range(F):
        a, b = map(str, sys.stdin.readline().split())
        
        if a not in parents:
            parents[a] = a
            roots[a] = 1
        if b not in parents:
            parents[b] = b
            roots[b] = 1
            
        parent_of_a = parents[a]
        parent_of_b = parents[b]
            
        if parent_of_a != parent_of_b:
            roots[parent_of_a] += roots[parent_of_b]
            
            try:
                for i in list_of_child[parent_of_b]:
                    list_of_child[parent_of_a].append(i)
                    parents[i] = parent_of_a
                del list_of_child[parent_of_b]
            except:
                pass
            #이것을 먼저 바꾸면 parents[parent_of_b] = parent_of_a가 된 상태에서 try문에 들어가서 의도와 달라진다.
            parents[parent_of_b] = parent_of_a 
            list_of_child[parent_of_a].append(parent_of_b)

        print(roots[parent_of_a])