사용자 도구

사이트 도구


ps:problems:boj:4195

친구 네트워크

ps
링크acmicpc.net/…
출처BOJ
문제 번호4195
문제명친구 네트워크
레벨골드 2
분류

Disjoint Set

시간복잡도O(n*α(n))
인풋사이즈n<=100,000
사용한 언어Python
제출기록65016KB / 356ms
최고기록260ms
해결날짜2022/06/24
태그

29단계

풀이

  • 그냥 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()

토론

댓글을 입력하세요:
F C U P W
 
ps/problems/boj/4195.txt · 마지막으로 수정됨: 2022/06/24 10:01 저자 teferi