6092 : 사이클 탐지 — 방향 그래프
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향 그래프가 주어졌을 때, 그래프 내에 사이클이 존재하는지 여부를 판별하는 프로그램을 작성하십시오.
방향 그래프에서의 사이클 탐지는 무방향 그래프와 달리 단순히 재방문 여부만으로 판별할 수 없습니다. DFS 탐색 과정에서 현재 탐색 경로상에 있는(아직 DFS가 종료되지 않은) 정점으로 향하는 간선(Back Edge)이 존재하는지 확인해야 합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 방향 그래프입니다.
방향 그래프에서의 사이클 탐지는 무방향 그래프와 달리 단순히 재방문 여부만으로 판별할 수 없습니다. DFS 탐색 과정에서 현재 탐색 경로상에 있는(아직 DFS가 종료되지 않은) 정점으로 향하는 간선(Back Edge)이 존재하는지 확인해야 합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 방향 그래프입니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 M (0 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v (u에서 v로 가는 간선)가 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v (u에서 v로 가는 간선)가 주어집니다.
출력 설명
사이클이 존재하면
YES, 존재하지 않으면 NO를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 2
2 3
3 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES도움
각 노드의 상태를 3가지(0: 방문 전, 1: 방문 중/DFS 종료 전, 2: 방문 완료/DFS 종료 후)로 관리하십시오. 1번 상태(GRAY)인 노드를 다시 만나면 사이클이 발견된 것입니다.