사용자 도구

사이트 도구


ps:problems:boj:28277

뭉쳐야 산다

ps
링크acmicpc.net/…
출처BOJ
문제 번호28277
문제명뭉쳐야 산다
레벨플래티넘 5
분류

smaller to larger

시간복잡도O(nlogn+q)
인풋사이즈n<=500,000, q<=500,000
사용한 언어Python 3.11
제출기록203132KB / 1632ms
최고기록1632ms
해결날짜2023/12/20

풀이

  • smaller to larger 을 사용하는 가장 기본적인 형태의 문제. 교육용으로 좋을 듯 하다
  • 각 집합을 set으로 관리해주면, 집합 S의 원소 한개를 집합 T에 추가하는 것을 O(1)에 처리할수 있다. 크기가 작은 집합의 원소들을 큰 쪽으로 합쳐준다면 총 시간복잡도는 O(nlogn)에 처리된다.
  • 집합의 크기를 구하는 것도 O(1)이므로 전체 시간복잡도는 O(q+nlogn)
  • 그냥 Disjoint Set을 쓸수 없는 이유는, 집합들이 disjoint 하지 않기 때문이다. 하나의 값이 여러집합에 포함되어있을수 있다.

코드

"""Solution code for "BOJ 28277. 뭉쳐야 산다".

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

Tags: [small to large]
"""

import sys


def main():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    S = []
    for _ in range(N):
        # pylint: disable=unused-variable
        n_i, *s_i = sys.stdin.readline().split()
        S.append(set(s_i))

    for _ in range(Q):
        match sys.stdin.readline().split():
            case ['1', a, b]:
                a, b = int(a) - 1, int(b) - 1
                if len(S[a]) < len(S[b]):
                    S[a], S[b] = S[b], S[a]
                S[a].update(S[b])
                S[b].clear()
            case ['2', a]:
                print(len(S[int(a) - 1]))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Y C᠎ C O N
 
ps/problems/boj/28277.txt · 마지막으로 수정됨: 2023/12/20 13:24 저자 teferi