https://www.acmicpc.net/problem/34012
문제요약
- 방향이 있는 그래프가 주어짐(노드 10만, 간선 50만)
- 사이클은 없음
- 모든 노드에서 도달 가능한 E가 존재
- E가 아닌 모든 노드에서 E로 가는 두 개의 겹치지 않는 경로를 만들기 위해 추가해야하는 최소 간선 개수 구하기
- 겹치지 않는다 : 같은 간선을 공유하지 않는다
접근법
- 처음에는 모든 경로를 찾아야하나 생각함
- E는 몇 개일까?
- 2개라면? E1 -> E2, E2 -> E1 을 가야하니까 사이클!
- 따라서 E는 1개
- E에 가장 가까운 노드를 고려한다면
- 그 노드에서 E로 가기위해
- 간선이 하나라면 -> 하나 추가
- 간선이 두개라면 -> 괜찮음
- 그 다음, 다음 노드들을 생각해보면
- 간선이 하나라면 -> 뭐가 되든 하나 추가
- 두개라면 -> 괜찮음
- E를 제외한 모든 노드에서 간선이 1개인 경우에만 추가하면 됨
newbieski