문제 링크
- http://icpc.me/16583
문제 출처
- 2018 Jakarta Regional K번
사용 알고리즘
- DFS
풀이
주어지는 그래프가 연결 그래프가 아닐 수 있지만, 각 컴포넌트를 따로따로 생각해주면 딱히 문제가 되지 않습니다.
컴포넌트에 간선이 $M$개 있을 때, 항상 $\lfloor \frac {M}{2} \rfloor$개의 부메랑을 찾을 수 있습니다.
각 컴포넌트가 트리라고 생각해봅시다.
각 트리의 자식 정점이 짝수 개라면 자식 2개와 자기 자신을 부메랑으로 묶어주면 됩니다. 홀수 개라면 자식과 자기 자신, 그리고 자신의 부모 노드를 묶어주면 됩니다.
입력으로 주어지는 것은 그래프이므로, 그래프에서 사이클을 없애서 트리처럼 만드는 방법을 시도할 수 있습니다.
위와 같은 그래프에는 사이클이 있어서 트리에서의 풀이를 적용할 수 없습니다.
“부메랑”이라는 것은 정점이 아닌 간선에만 영향을 받기 때문에, 아래 사진처럼 더미 정점을 추가해주면 트리 형태로 바꿀 수 있고, 트리에서의 풀이를 그대로 적용할 수 있습니다.
구현은 생각보다 매우 간단합니다.