すべてのノードの削除に必要な操作の予想数をカウントするC++プログラム

有向グラフGの隣接行列があるとします。グラフが空になるまで、次の操作を繰り返します。Gから1つの頂点を選択し、その頂点と、その頂点から到達可能なすべての頂点を、いくつかのエッジをたどって消去します。頂点を消去すると、それに付随するエッジも消去されます。操作が行われると予想される回数を見つける必要があります

したがって、入力が次のような場合

最初に頂点Aを選択し、すべての頂点を削除します。頂点Bを選択し、BとCを削除し、2番目の操作でAを選択して削除します。同様に、Cを選択すると、2つの操作が必要になります。したがって、平均は（1 + 2 + 2）/ 3=1.6667です。

ステップ

これを解決するには、次の手順に従います-

n := size of G
for initialize i := 0, when i < n, update (increase i by 1), do:
   G[i, i] := 1
for initialize k := 0, when k < n, update (increase k by 1), do:
   for initialize i := 0, when i < n, update (increase i by 1), do:
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[i, k] is non-zero and G[k, j] is non-zero, then:
            G[i, j] := 1
         ans := 0
      for initialize i := 0, when i < n, update (increase i by 1), do:
         k := 0
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[j, i] is non-zero, then:
            (increase k by 1)
         ans := ans + 1.0 / k
return ans

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

double solve(vector<vector<int>> G){
   int n = G.size();
   for (int i = 0; i < n; ++i)
      G[i][i] = 1;
   for (int k = 0; k < n; ++k)
      for (int i = 0; i < n; ++i)
         for (int j = 0; j < n; ++j)
            if (G[i][k] && G[k][j])
               G[i][j] = 1;
   double ans = 0;
   for (int i = 0; i < n; ++i){
      int k = 0;
      for (int j = 0; j < n; ++j)
         if (G[j][i])
            ++k;
         ans += 1.0 / k;
   }
   return ans;
}
int main(){
   vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
   cout << solve(G) << endl;
}

入力

{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }

出力

1.66667