C++の無向グラフの連結成分の数

n個のノードがあり、それらに0からn -1のラベルが付けられ、無向エッジのリストも与えられているとすると、無向グラフで連結成分の数を見つけるために1つの関数を定義する必要があります。

したがって、入力がn =5で、edges =[[0、1]、[1、2]、[3、4]]、

その場合、出力は2になります

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

• 関数dfs（）を定義します。これにより、ノード、グラフ、visitedという配列が取得されます。

• visited [node]がfalseの場合、-

  • 訪問済み[ノード]：=true

• 初期化i：=0の場合、i <グラフ[ノード]のサイズの場合、更新（iを1増やします）、実行-

  • dfs（graph [node、i]、graph、visited）

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

• サイズnの訪問された配列を定義します

• nがゼロ以外の場合、-

  • 配列グラフを定義する[n]

• 初期化i：=0の場合、i <エッジのサイズの場合、更新（iを1増やします）、実行-

  • u：=エッジ[i、0]

  • v：=エッジ[i、1]

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

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

• ret：=0

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

  • 訪問されていない場合[i]がゼロ以外の場合、-

    • dfs（i、graph、visited）

    • （retを1増やします）

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   void dfs(int node, vector<int< graph[], vector<bool>& visited){
      if(visited[node]) return;
         visited[node] = true;
      for(int i = 0; i < graph[node].size(); i++){
         dfs(graph[node][i], graph, visited);
      }
   }
   int countComponents(int n, vector<vector<int<>& edges) {
      vector <bool> visited(n);
      if(!n) return 0;
         vector <int< graph[n];
      for(int i = 0; i < edges.size(); i++){
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      int ret = 0;
      for(int i = 0; i < n; i++){
         if(!visited[i]){
            dfs(i, graph, visited);
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int<> v = {{0,1},{1,2},{3,4}};
   cout << (ob.countComponents(5, v));
}

入力

5, [[0,1],[1,2],[3,4]]

出力

2