C++のネットワークにおける重要な接続

n台のサーバーがあるとします。そして、これらは0からn-1まで番号が付けられ、無向のサーバー間接続によって接続され、ネットワークを形成します。ここで、connections [i] =[a、b]はサーバーaとbの間の接続を表します。すべてのサーバーは、直接または他のサーバーを介して接続されています。ここで、重要な接続とは、それが削除されると、一部のサーバーが他のサーバーに到達できなくなる接続です。重要な接続をすべて見つける必要があります。

したがって、入力がn =4で、接続=[[0,1]、[1,2]、[2,0]、[1,3]]、

その場合、出力は[[1,3]]

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

• 1つのセットを定義する

• アレイディスクを定義する

• 配列を低く定義する

• 1つの2D配列retを定義する

• 関数dfs（）を定義します。これにより、ノード、パー、1つの2D配列グラフが取得されます。

• ノードが訪問済みの場合、-

  • 戻る

• 訪問先にノードを挿入

• disc [node]：=time

• low [ノード]：=時間

• （時間を1つ増やします）

• グラフ[ノード]

  のすべての要素xについて

  • xがparと同じ場合、-

    • 次の部分を無視し、次の反復にスキップします

  • xが訪問されていない場合、-

    • dfs（x、node、graph）

    • low [node]：=low[node]とlow[x]

      の最小値

    • disc [node]

      • retの最後に{node、x}を挿入します

  • それ以外の場合

    • low [node]：=low[node]とdisc[x]

      の最小値

• メインの方法から、次のようにします-

  • ディスクのサイズをn+1に設定

  • サイズをn+1に設定

  • 時間：=0

  • サイズグラフn+1

    のリストの配列を定義します

  • 初期化i：=0の場合、i

    • u：=v [i、0]

    • w：=v [i、1]

    • グラフの最後にwを挿入します[u]

    • グラフの最後にuを挿入します[w]

  • dfs（0、-1、グラフ）

  • retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   set<int> visited;
   vector<int> disc;
   vector<int> low;
   int time;
   vector<vector<int> > ret;
   void dfs(int node, int par, vector<int> graph[]) {
      if (visited.count(node))
      return;
      visited.insert(node);
      disc[node] = low[node] = time;
      time++;
      for (int x : graph[node]) {
         if (x == par)
         continue;
         if (!visited.count(x)) {
            dfs(x, node, graph);
            low[node] = min(low[node], low[x]);
            if (disc[node] < low[x]) {
               ret.push_back({ node, x });
            }
         } else{
            low[node] = min(low[node], disc[x]);
         }
      }
   }
   vector<vector<int> > criticalConnections(int n, vector<vector<int> >& v) {
      disc.resize(n + 1);
      low.resize(n + 1);
      time = 0;
      vector<int> graph[n + 1];
      for (int i = 0; i < v.size(); i++) {
         int u = v[i][0];
         int w = v[i][1];
         graph[u].push_back(w);
         graph[w].push_back(u);
      }
      dfs(0, -1, graph);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,2},{2,0},{1,3}};
   print_vector(ob.criticalConnections(4,v));
}

入力

4, {{0,1},{1,2},{2,0},{1,3}}

出力

[[1, 3, ],]