방향 그래프의 사이클 판별
실버 II의견: 0
정점이 \(n\) 개, 간선이 \(m\) 개인 방향 그래프가 주어진다. 간선은 \(u \to v\) 처럼 방향이 있다.
이 그래프에 사이클이 존재하는지 판별하여라. 사이클이란 어떤 정점에서 출발하여 간선 방향을 따라 이동했을 때 다시 그 정점으로 돌아올 수 있는 경로를 말한다(즉, 어떤 정점에서 시작해 자기 자신으로 돌아오는 길이 \(1\) 이상의 닫힌 경로가 존재하면 된다).
그래프에는 자기 자신으로 가는 간선(셀프 루프)과 중복된 간선은 없다.
\(1 \le n \le 2 \cdot 10^5\)
\(0 \le m \le 2 \cdot 10^5\)
셀프 루프와 중복 간선은 없다.
첫째 줄에 정점의 수 \(n\) 과 간선의 수 \(m\) 이 공백으로 구분되어 주어진다.
다음 \(m\) 개의 줄에 각각 두 정수 \(u\), \(v\) 가 주어지며, 이는 \(u\) 에서 \(v\) 로 가는 방향 간선을 뜻한다 (\(1 \le u, v \le n\), \(u \ne v\)).
그래프에 방향 사이클이 존재하면 YES, 존재하지 않으면 NO 를 한 줄에 출력한다.
3 3
1 2
2 3
3 1
YES
\(1 \to 2 \to 3 \to 1\) 로 돌아오는 사이클이 있으므로 YES.
3 3
1 2
2 3
1 3
NO
모든 간선이 한 방향으로만 흐르는 DAG 라 사이클이 없다. NO.
2 2
1 2
2 1
YES
\(1 \to 2 \to 1\) 은 길이 \(2\) 의 사이클이다. YES.
riseoj 작성
출처 Original
평가 및 의견
방향 그래프의 사이클 판별
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
방향 그래프의 사이클 판별