Count number of nodes in each connected part of an undirected unweighted graph

Question

I am new to C++ STL and have started Graph Theory recently. After referring to https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/, I can count the number of connected components in an undirected, unweighted graph using DFS as:

#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;
}

But how do we count the total number of nodes in each component?

For example: In this graph, see image there are 3 connected components, with no. of nodes being 3, 2 , and 1 respectively.

`#include ` -- [Don't do this](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — PaulMcKenzie, Jun 14 '18 at 09:17
Thank you for this additional information sir. I won't use it now :) — Tanya Sethi, Jun 14 '18 at 11:18

score 6 · Accepted Answer · answered Jun 14 '18 at 09:02

6

You could maintain a dummy variable count with each call to DFS from main()

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);        
  }    
}

and

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";
  }        
}

Or you could refer to the change in visited vector(number of new 1's in it) after every call to DFS() from main()

answered Jun 14 '18 at 09:02

Gaurav Sehgal

7,422
2
18
34

For this line "DFS(v[start][i], v, visited);" wouldn't calling a function with without passing the required number of arguments cause error – Ghos3t Jun 02 '20 at 01:07
1

@Ghos3t - It sure will. we need to pass the count as well by reference. DFS(v[start][i], v, visited, count); – Tanya Sethi Jun 14 '20 at 15:14

score 1 · Answer 2 · answered Jun 14 '18 at 09:05

you can maintain a global variable no_of_nodes which will be set to zero at start of dfs of each component and incremented by one when you visit each node in that component.

#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;
}

Count number of nodes in each connected part of an undirected unweighted graph

2 Answers2