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;

}