테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 뭉쳐야 산다 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}