Algorithm/Acmicpc
1976 여행 가자 [JAVA]
문제 분석https://www.acmicpc.net/problem/1976N개의 도시와 각 도시와 연결된 도시들에 대한 정보가 주어진다.M개의 도시 방문 경로가 가능한 경로인 지 확인하여 가능하다면 YES 아니면 NO를 반환하면 되는 문제다, 여기서 경로에 대해 최적인지 판단할 필요가 없다.따라서, 두 도시 사이에 어떠한 길이의 경로로든 연결만 되어 있다면 갈 수 있게 된다. 그렇기에 union find로 각 도시의 부모를 하나 정하고 두 도시의 부모 idx가 동일하면 같은 집합임을 의미하고 이는 곧 서로의 도시로 갈 수 있다는 뜻이 된다. 주의할 점은, m개의 방문 도시를 0,1, .. 이렇게 주는게 아닌, 1,2,... 이렇게 주니 인덱스를 애초에 1부터하던가 아니면 M개의 도시의 인덱스를 1 빼고 ..
