C++中无向图连通分量的数量

假设我们有n个节点，它们从0到n-1标记，并且还给定了一个无向边的列表，我们需要定义一个函数来查找无向图中连通分量的数量。

因此，如果输入类似于n=5，edges=[[0, 1], [1, 2], [3, 4]]，

则输出将为2

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数dfs()，它将接收节点、图和一个名为visited的数组作为参数，

• 如果visited[node]为假，则：

  • visited[node] := true

• 对于初始化i:=0，当i < graph[node]的大小，更新（i增加1），执行：

  • dfs(graph[node, i], graph, visited)

• 从主方法执行以下操作：

• 定义一个大小为n的数组visited

• 如果n不为零，则：

  • 定义一个数组graph[n]

• 对于初始化i:=0，当i < edges的大小，更新（i增加1），执行：

  • u := edges[i, 0]

  • v := edges[i, 1]

  • 在graph[u]的末尾插入v

  • 在graph[v]的末尾插入u

• ret := 0

• 对于初始化i:=0，当i < n，更新（i增加1），执行：

  • 如果visited[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

Arnab Chakraborty

更新于: 2020年11月18日

2K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习