6091 : 사이클 탐지 — 무방향 그래프
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 그래프가 주어졌을 때, 그래프 내에 사이클(Cycle)이 존재하는지 여부를 판별하는 프로그램을 작성하십시오.
무방향 그래프에서의 사이클 탐지는 DFS를 수행하면서 이미 방문한 정점을 재방문했는지 확인해야 합니다. 다만, 직전 부모 노드로 되돌아가는 간선은 사이클로 판정하지 않습니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 무방향이며, 직전 부모 노드로의 역방향 간선은 사이클로 판정하지 않습니다.
무방향 그래프에서의 사이클 탐지는 DFS를 수행하면서 이미 방문한 정점을 재방문했는지 확인해야 합니다. 다만, 직전 부모 노드로 되돌아가는 간선은 사이클로 판정하지 않습니다.
[제약 조건]
• 정점 수 $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가 주어집니다.
둘째 줄부터 M개의 줄에 간선 u v가 주어집니다.
출력 설명
사이클이 존재하면
YES, 존재하지 않으면 NO를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
2 3
3 4
4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES도움
DFS 함수 호출 시 부모 노드 정보를 함께 넘겨주어(예:
dfs(node, parent)), 다음 노드가 이미 방문되었는데 그 노드가 parent가 아니라면 사이클이 존재하는 것으로 판단할 수 있습니다.