计算无向无权图中每个连通部分的节点数

Question

我刚接触C++ STL，并最近开始学习图论。 在参考https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/后，我可以使用DFS计算无向无权图中连通组件的数量：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int connected=0, temp1, temp2,n, p;

void DFS(int start, vector<int> v[],vector<int> &visited) {
    visited[start] = 1;
    for(int i= 0; i<v[start].size(); ++i) {        
        if(visited[v[start][i]] == 0)
            DFS(v[start][i], v, visited);        
    }    
}

int main() {
    cin>>n>>p; // number of vertices and edges
    vector<int> v[n+1], visited(n+1,0);
    for(int i=0; i<p; ++i) {
        cin>>temp1>>temp2;
        v[temp1].push_back(temp2);
        v[temp2].push_back(temp1);
    }     
    connected = 0;
    for(int i=1;i<=n;++i) {
        if(visited[i] == 0 ) {
            connected++;
            DFS(i,v,visited);
        }        
    }
    cout<<connected<<endl;    
return 0;
}

但是我们如何计算每个连通分量中节点的总数？

例如：在这个图中，查看图片有三个连通分量，分别具有3、2和1个节点。

- Tanya Sethi

---

不要这样做：#include <bits/stdc++.h>。请参考这里。 - PaulMcKenzie

不要这样做。 - Ashutosh Kumar Verma

感谢您提供的额外信息，先生。我现在不会使用它 :) - Tanya Sethi

Answer 1

你可以在每次从main()调用DFS时维护一个虚拟变量count。

void DFS(int start, vector<int> v[],vector<int> &visited, int &count)
{
  visited[start] = 1;
  count++;
  for(int i= 0; i<v[start].size(); ++i)
  {        
    if(visited[v[start][i]] == 0)
        DFS(v[start][i], v, visited);        
  }    
}

并且

for(int i=1;i<=n;++i)
{
  if(visited[i] == 0 )
  {
     connected++;
     int count=0;
     DFS(i,v,visited,count);
     cout<<"This component has "<<count<<" nodes"<<"\n";
  }        
}

或者你可以参考每次从main()调用DFS()后visited向量（其中新1的数量）的变化。

- Gaurav Sehgal

---

对于这行代码 "DFS(v[start][i], v, visited);"，如果调用函数时没有传递所需的参数数量，会导致错误吗？ - Ghos3t

@Ghos3t - 当然需要。我们还需要通过引用传递计数器。 DFS(v[start][i], v, visited, count); - Tanya Sethi

Answer 2

你可以维护一个全局变量no_of_nodes，在每个连通分量的dfs开始时将其设置为零，并在访问该连通分量中的每个节点时将其递增一次。

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int connected=0, temp1, temp2,n, p;

int no_of_nodes=0;


void DFS(int start, vector<int> v[],vector<int> &visited) {
    visited[start] = 1;
    no_of_nodes++;
    for(int i= 0; i<v[start].size(); ++i) {        
    if(visited[v[start][i]] == 0)
        DFS(v[start][i], v, visited);        
    }    
}

int main() {
    cin>>n>>p; // number of vertices and edges
    vector<int> v[n+1], visited(n+1,0);
    for(int i=0; i<p; ++i) {
    cin>>temp1>>temp2;
    v[temp1].push_back(temp2);
    v[temp2].push_back(temp1);
    }     
    connected = 0;
    vector<int>nodes;
    for(int i=1;i<=n;++i) {
    if(visited[i] == 0 ) {
        connected++;
        no_of_nodes=0;
        DFS(i,v,visited);
        nodes.push_back(no_of_nodes);
    }        
    }
    cout<<connected<<endl;    
return 0;
}

- Ashutosh Kumar Verma