MungGu Story

백준 17171번, 집합의표현 문제 알아보기 1717번, 집합의 표현 문제는 disjoint-set, 서로소 집합 관련 문제입니다. 서로소 집합 개념은 MST문제을 풀때 자주 사용하는 크루스컬 알고리즘에서도 활용되는 유용한 개념입니다. 본 문제 난이도는 solved.ac기준, 골드4로 일반 코딩테스트 기준, 중후반대에 나올 수 있는 문제입니다. 시간제한은 2초, 메모리 제한은 128MB입니다. 초기에 {0}, {1}, {2}, .... {N}의 N+1개 집합이 있다고 할때, 이에 대한 합집합 연산, 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 출력하는 문제입니다. 이렇게까지만 문제를 보면 단순한 문제로 보일 수도 있지만, N의 입력범위가 최대 백만이란 점에서, disjoined-set 기반의 ..