問題：
無向グラフは、サイクルが 1 つだけ含まれている場合、単循環です。与えられたグラフ G が単環かどうかを判定する O( |V| + |E| ) アルゴリズムを説明してください。
私の解決策：
整数 i = 0
G で変更された DFS を実行します。ここでは、既にアクセスされているため、頂点にアクセスしないと決定するたびに i をインクリメントします。
DFS が実行された後、i==1 の場合、グラフは単循環です。
この解決策はうまくいくと思いましたが、それが間違っていることを証明する反例があるかどうか疑問に思っています。誰かがそれを明確にすることができれば、ありがとう。
"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