Header Ads Widget



Connected Components in a Graph


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.


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
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.

using namespace std;
vector<int > arr[100001];
int visited[100001];

// function of dfs
void dfs(int n)
    for(int child:arr[n])

// Driver program
int main()
    int n,e;
int a,b;
    for(int i=0;i<e;i++)
    int count=0;
    for(int i=1;i<=n;i++)
    return 0;

Post a Comment