(백준/c++) 1976번 - 여행 가자

1976번: 여행 가자 (acmicpc.net)

1976번: 여행 가자

1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 

2. 풀이: 문제에 나와 있는 거 문장을 보면 `같은 도시를 여러 번 방문하는 것도 가능하다.`라고 나와 있다. 여행 계획의 시작 지점을 시작으로 경로를 가기 위한 edge가 이어져 있다면 어떤 방법으로든 여행 계획을 한 번씩 들려서 목적지까지 도달할 수 있다. 밑에는 백준 문제에 예시를 그림으로 표현하고 배열의 인덱스에 맞는 value 값을 표현한 것이다. 

이처럼 여행 계획의 경로를 가리키는 value가 모두 같은 값일 때 목적을 달성할 수 있고 value가 하나라도 다르면 목적을 달성할 수 없다.

3. 구현