백준 1178 간선 추가

https://www.acmicpc.net/problem/1178

1178번: 간선 추가

답이 되는 그래프는 한붓그리기가 가능해야 한다. 문제에서 주어진 그래프가 하나의 컴포넌트라는 보장이 없으므로, 이 컴포넌트를 하나로 합치는 동시에 홀수점의 개수가 0이나 2인 한붓그리기의 조건을 만족해야 한다. 

 

풀이를 생각해 보면, 한붓그리기가 가능한 두 컴포넌트는 한 컴포넌트에서 한붓그리기의 끝 정점과 나머지 컴포넌트에서 한붓그리기의 시작 정점을 연결하는 간선을 추가하여 한붓그리기가 가능한 하나의 컴포넌트로 만들 수 있다. 

 

즉, Union-Find를 써서 컴포넌트를 나누고, 각 컴포넌트에서 홀수점의 개수가 0또는 2가 되도록 간선을 추가하고, (컴포넌트-1) 의 간선을 추가하면 된다. 

 

처음에는 이미 있는 간선을 내가 또 추가하면 안 된다고 생각했는데, 애초에 그렇게 하면 답이 없는 케이스가 있으니까 신경쓰지 말고 그냥 하면 된다.