SCC. [3977]

[1. 문제 설명]

다른 모든 구역에 도달할 수 있는 시작 구역을 찾는다.

없으면, Confused 를 출력하고,

있다면, 시작 구역을 오름차순으로 출력한다.

---

[2. 풀이 접근]

A. 단순한 풀이

• dfs 를 수행하여 모든 정점에 도달 할 수 있는 경우가 시작 구역이 된다.
• 모든 정점을 대상으로 dfs 를 수행한다.
• 단, 시간 초과가 발생하므로, 이 풀이는 폐기해야 한다.

B. SCC 를 이용한 풀이

• 같은 SCC 에 속한 노드들은 항상 그 경로가 존재한다.
• 이러한 특성을 이용하여 SCC 에서 SCC 로 이동 하는 경우를 생각한다.
• 어떤 SCC 에서 다른 SCC 를 모두 방문할 수 있다면, 이 SCC 에 속한 노드만 출력하면 되기 때문이다.
• 방향 그래프에서 각 SCC 사이를 연결하는 간선들을 모으면, SCC 들을 정점으로 하는 DAG 를 만들 수 있다.
• 이 DAG 의 root 가 될 수 있는 SCC 를 찾도록 한다.
• SCC 를 노드로 하는 그래프에서 incoming edge 개수가 없는 SCC 가 찾고자 하는 SCC 가 된다.
• 단, 이러한 SCC 가 2개 이상인 경우, 이 SCC 간 서로 연결될 수 없으므로, Confused 를 출력해야 한다.

---

[3. 코드]