https://www.acmicpc.net/problem/30870
문제요약
- 주어진 그래프에서 시간마다 인접한 노드를 지워나감. 물론 최초에 지울 노드는 있고
- 이렇게 지우다가 최초로 사이클이 생기지 존재하지 않는 시간 구하기
- 노드, 간선 : 20만
접근법
- 매번 지울때마다 사이클을 판단하기에는 시간복잡도가 너무 높음
- 간선이 언제 지워지는지는 알겠음 : BFS를 적절히 응용
- 지워지는 역순으로 간선을 연결해나가가다가 사이클이 생기는 시점 판단
- 사이클 판단은 union-find로 판단 : merge가 안되는 경우 = 이미 같은 부모 = 사이클
newbieski