집합의 표현
문제 링크
- http://icpc.me/1717
풀이
Union Find 구현
여행 가자
문제 링크
- http://icpc.me/1976
풀이
그래프에서 연결요소가 1개인지 확인
친구비
문제 링크
- http://icpc.me/16562
풀이
union을 해주면서 mn[x] = x번째와 친구가 되기 위한 친구비의 최소 비용 을 구해주자.
공항
문제 링크
- http://icpc.me/10775
풀이
set + lower_bound를 이용해 그리디하게 해결
풀이
방 청소
문제 링크
- http://icpc.me/9938
풀이
술병을 A에서 B로 옮길 수 있다면 방향이 있는 간선(A, B)로 연결해주자.
한 정점에서 뻗어나가는 간선은 하나밖에 없으므로 Union Find로 관리하면 된다.
문명
문제 링크
- http://icpc.me/14868
풀이
네트워크 연결
문제 링크
- http://icpc.me/1922
풀이
MST 구현
전력난
문제 링크
- http://icpc.me/6497
풀이
MST 구현
도시 분할 계획
문제 링크
- http://icpc.me/1647
풀이
두 그룹으로 나누면 된다.
MST를 만들 때 V-1개의 간선이 아닌 V-2개의 간선으로 만들어주면 두 그룹으로 나눌 수 있다.
행성 터널
문제 링크
- http://icpc.me/2887