1976번: 여행 가자 www.acmicpc.net 이 문제는 도시들이 정점으로 주어진 그래프에 대해 여행 계획이 주어진 경우 그래프 내 간선을 통해 해당 여행 계획을 실천할 수 있는지를 묻는 문제이다. 이를 달리 해석하면 여행 계획 내 도시들이 그래프 내에서 모두 연결되어 있는지를 묻는 문제로, 이는 그래프 탐색을 통해 여행 계획 내 정점들이 모두 연결되어 있는지를 확인함으로써 해결할 수 있다. 즉, 우선 여행 계획 내 한 도시에 대해 DFS나 BFS를 실행한 뒤에, 여행 계획 내 나머지 도시들을 방문했었는지를 검사하면 된다. 그러나 이 문제는 다른 방식으로도 해결할 수 있는데, 바로 분리 집합을 이용하는 것이다. 우선 각 도시에 대해 그 도시를 유일한 원소로 가지는 집합을 만든다. 그 다음 만약 두 ..
