일반 그래프 사이클 감지 (내 대답 확인하십시오)

Question

문제 :

정확히 1 사이클이 포함 된 경우 무향 그래프는 unicyclic입니다. 주어진 그래프 G가 단일 고리인지 아닌지를 결정하기위한 O (| V | + | E |) 알고리즘을 기술하십시오.

내 솔루션 :

INT의 전 = 0

실행 우리는 내가 매번 우리가 이미 방문했기 때문에 정점을 방문하지 않기로 결정 증가 G에 수정 된 DFS.

DFS가 완료된 후 i == 1이면 그래프가 단일 체인입니다.

나는이 해결책이 효과가있을 것이라고 생각했지만 그것이 거짓임을 입증 할 수있는 반례가 있는지 궁금해하고 있습니다. 누구든지 위대한 것이라고 분명히 할 수 있다면, 고마워.

Answer 1

그래프가 연결된 단일 구성 요소로 구성되어 있습니까?

이 경우 꼭지점과 가장자리를 계산하고 | V |를 확인하십시오. - | E | = 0

그렇지 않으면 연결된 구성 요소의 수를 계산하십시오. O (| V | + | E |), 및 | V | - | E | = 연결된 구성 요소의 수 - 1

참고 : 연결된 구성 요소가 둘 이상인은 알고리즘과 반비례입니다.

Answer 2

"Increment i everytime we decide not to visit a vertex because 
it has already been visited." 

여기에서 무엇을하려하는지 명확하지 않습니다.

오히려 다음이 이것에 대해 어떻게 :

는 DFS를 수행하고 다시 모서리의 수를 계산합니다.

A back edge is an edge that is from a node to itself (selfloop) or one of its 
ancestor in the tree produced by DFS. 

뒷면의 수 == 1이면 외발 자전거는 그렇지 않습니다.

To count number of back edges, follow this algorithm. 

To detect a back edge, we can keep track of vertices currently in recursion stack of 
function for DFS traversal. If we reach a vertex that is already in the recursion stack, 
then there is a cycle in the tree. The edge that connects current vertex to the 
vertex in the recursion stack is back edge