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()
ps/problems/boj/28277.txt · 마지막으로 수정됨: 2023/12/20 13:24 저자 teferi
토론