공통
유니온할 때, 어차피 같은 집합이므로 (첫 시작 정점, 현재 정점)으로 해도 됨
- 16236 (아기 상어)
- 먹을 수 있는 물고기를 모두 찾으면서, 문제 조건에 맞는 물고기를 마지막에 찾아야 함
- 18111 (마인크래프트)
- 탐색 범위를 가장 낮은 땅 ~ 가장 높은 땅으로 하는게 효율적
- 1043 (거짓말)
- 유니온을 할 때, 둘 중 하나가 진실을 아는 사람이라면 두 루트 모두 진실을 알도록 구현
- 각 파티에서 한 사람만 알아도 거짓말 가능 여부를 판단할 수 있음
- 1976 (여행 가자)
- 마지막에 주어진 경로가 가능한지 살펴볼 때, 꼭 바로 전과 현재를 비교할 필요 없음. 처음 시작 정점과 현재 정점 비교도 가능
- 10775 (공항)
- 16724 (피리 부는 사나이)
- 20040 (사이클 게임)
- union 연산 함수를 bool 반환형으로 만들면 사이클이 발생하는 순간을 판단하기 좋음
- 가장 큰 정사각형 찾기
- dp[0][], dp[][0]을 더미 인덱스로 만들면 따로 처리할 필요 없이 한 번에 깔끔하게 가능