문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

이러한 경우에는 0, 1, 2 에서 시작하면 모든 구역에 도달할 수 있고,

이러한 경우에는 모든 구역에 도달할 수 있는 시작 지점이 없다.

시작 지점을 제외한 다른 모든 구역은 최소한 어느 한 구역으로부터 접근 가능해야 한다.
즉, SCC로 묶었을 때, in_degree가 0인 것이 딱 한 덩어리만 있어야 한다.

Algorithm

1. SCC를 구한다. 이때, 각 SCC 집합은, SCC 중 하나를 대표 node로 삼아 구분한다.
2. SCC 집합 별로 In_degree를 구한다. DFS를 하여, 다른 SCC로부터 접근 가능하면 해당 집합의 indegree를 늘려주면 된다.
3. In_degree가 0인 SCC 집합이 한 가지뿐이라면, 해당 집합의 원소를 모두 출력한다.

Data Structure

• adjList[]: 그래프를 나타내기 위한 adjacency List

결과

Other

시간 복잡도는 매 케이스 마다 O(N+M)이다.