グラフ内の無用なエッジを見つけよう

Question

Nのグラフが一緒に接続されているので、無駄なエッジの数を見つけなければなりません。
エッジを削除すると、エッジが役に立たないと言われ、グラフ全体がまだ接続されています。
私のアプローチ
DFSを実行し、訪問したノードの数を2回以上数えます。

public static void search_me(int i , int pa){ 

     V[i]=true; 
     for(int j:maps[i]){ 


       if(!V[j]){ 
       search_me(j,i); 

       }else if(pa!=j){ 
        useless++; 
       } 

     } 

} 

しかし、それは私に正解を与えていません。それにはどのような正しいアプローチがありますか？

Answer 1

Tarjan'sアルゴリズムを使用すると、O（n）内の各コンポーネント内のすべてのブリッジを見つけることができます。ブリッジは、その削除によってグラフが切断されるエッジです。 次に、必要な番号が続きます。グラフのエッジの数 - ブリッジの数。

Answer 2

グラフが最初に接続されている場合は、正確にn-1エッジを持つスパニングツリーが割り当てられます。ここで、nは頂点の数です。この現象については、hereを参照してください。したがって、最初のグラフがmの辺を有する場合、無駄な辺の数はm - (n - 1) = m - n + 1であり、これはグラフアルゴリズムなしで直接決定することができる。