BOJ 1976 - 여행 가자

링크: https://www.acmicpc.net/problem/1976

문제

\(n\)개의 도시 사이의 연결 상태가 인접 행렬로 주어지고 여행 계획에 있는 \(m\)개의 도시가 주어질 때, \(m\)개의 도시를 모두 방문할 수  있는가를 묻는 문제이다.

다시말하면, \(m\)개의 도시가 모두 연결되어있는가를 확인하면 된다.

이 문제는 서로소 집합(Disjoint-Set)으로 간단하게 해결할 수 있다. 각 도시들의 연결 상태만 확인하면 되므로, 연결된 도시들을 집합으로 묶어서 표현한 후 마지막에 주어지는 \(m\)개의 도시들이 모두 같은 집합에 속하는 지 확인하면 정답이기 때문이다.

코드