I Want to Cycle.

사이클과 관련된 정보는 강한 연결 요소를 이용해 처리할 수 있다.

먼저 주어진 유향 그래프를 강한 연결 요소로 압축한다. 크기가 $2$ 이상인 강한 연결 요소는 그 안에 사이클을 포함한다. 입력에서는 자기 자신으로 가는 간선이 주어지지 않으므로, 크기가 $1$인 강한 연결 요소는 사이클을 포함하지 않는다.

강한 연결 요소를 하나의 정점으로 압축하면 DAG가 된다. 어떤 원래 정점에서 사이클을 방문할 수 있는지는, 그 정점이 속한 강한 연결 요소에서 사이클을 포함하는 강한 연결 요소로 도달할 수 있는지와 같다.

따라서 다음과 같이 해결할 수 있다.

• 그래프의 모든 강한 연결 요소를 구한다.
• 크기가 $2$ 이상인 강한 연결 요소를 사이클을 포함하는 강한 연결 요소로 표시한다.
• 강한 연결 요소 DAG의 역방향 간선을 만든다.
• 사이클을 포함하는 강한 연결 요소들에서 시작해 역방향 간선을 따라 DFS 또는 BFS를 한다.

이렇게 방문된 강한 연결 요소들은 원래 방향으로 어떤 사이클을 포함하는 강한 연결 요소에 도달할 수 있다. 따라서 방문되지 않은 강한 연결 요소에 속한 정점들이 답에 포함된다.

시간 복잡도는 $O(N+M)$이고, 메모리 복잡도는 $O(N+M)$이다.