Connected Components in a Graph

 Problem:-

Given n, i.e. total number of nodes in an undirected graph numbered from 1 to n and an integer e, i.e. total number of edges in the graph. Calculate the total number of connected components in the graph. A connected component is a set of vertices in a graph that are linked to each other by paths.

Input Format:

First line of input line contains two integers n and e. Next e line will contain two integers u and v meaning that node u and node v are connected to each other in undirected fashion. 

Output Format:

For each input graph print an integer x denoting total number of connected components.

Constraints:

All the input values are well with in the integer range.

Sample Input
8 5
1 2
2 3
2 4
3 5
6 7
Sample Output
3
Time Limit: 5
Memory Limit: 256

(c++) Code:-

  First we take a vertex which is not visited then traverse all the graph where we can reach by this vertex . and increase  the value of count . in first cycle (calling first time dfs function) we change the visited value of all the vertex which is visited 0 to 1 . then take second vertex which is not visited. and so on.

#include<bits/stdc++.h>
using namespace std;
vector<int > arr[100001];
int visited[100001];

// function of dfs
void dfs(int n)
{
    visited[n]=1;
    for(int child:arr[n])
    {
        if(visited[child]==0)
         dfs(child);
    }
}

// Driver program
int main()
{
    int n,e;
int a,b;
    cin>>n>>e;
    for(int i=0;i<e;i++)
    {
        cin>>a>>b;
        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    int count=0;
    for(int i=1;i<=n;i++)
    {
        if(visited[i]==0)
         dfs(i),count++;
    }
    cout<<count;
    return 0;
}



Leave a Reply

Your email address will not be published.