4195: 친구 네트워크

풀이 시간

• 33m

구현 방식

• 이 문제의 포인트는, count 딕셔너리 변수를 이용해서 {"사용자의 아이디": 그래프의 노드 개수} 형식으로 값을 저장하고 이를 이용해 문제에서 원하는 정답을 빠르게 찾아줘야한다는 점이었다

• union 함수에서 parent와 count의 값을 모두 a에 합쳐준다

• edge를 입력받을 때마다 위와 같이 union을 수행해준다면, a의 루트 부모 노드에 해당하는 count 값이 구하고자 하는 정답이된다

코드

import sys

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a); b = find(b)
    if a != b: #parent랑 count 모두 a에 합쳐줌
        parent[b] = a
        count[a] += count[b]

T = int(sys.stdin.readline()[:-1])
for t in range(T):
    F = int(sys.stdin.readline()[:-1])

    parent = dict(); count = dict()
    for f in range(F):
        a, b = map(str, sys.stdin.readline()[:-1].split())

        if a not in parent:
            parent[a] = a; count[a] = 1
        if b not in parent:
            parent[b] = b; count[b] = 1

        if find(a) != find(b):
            union(a, b)

        print(count[find(a)])

결과