[BOJ]9466번: 텀 프로젝트

 

문제: https://www.acmicpc.net/problem/9466

---

싸이클 찾기 문제입니다.

위상 정렬을 통해 해결할 수 있습니다.

 

싸이클의 대상이 아닌 노드의 특징은 자신에게 들어오는 간선이 하나도 없다는 점입니다.

 

그러므로 처음에 데이터를 입력받을 때 finished[] 배열을 통해서 자신에게 들어오는 간선을 카운트 해줍니다.

 

1. finished[Node] == 0인 애들을 제외 (싸이클이 아님)

2. 1번에서 제외된 노드들과 연결되어있던 Node들의 finisehd[] 값을 1 감소시켜줍니다. 

(싸이클이 아닌 후보들로부터 들어온 간선은 싸이클에 아무런 영향을 끼치지 못하므로)

 

3. 2번 과정을 통해 finished[] == 0인 애들이 있다면 이 노드들도 제외해줍니다.

4. finished[] == 0인 노드가 없을 때까지 2-3번 과정을 반복해줍니다.

---

풀이: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9466.cc