pranay_teja
10/23/2018 - 6:34 AM

## Graphs-ConnectedComponents

``````#include<bits/stdc++.h>
using namespace std;

// #Graph
// Both Directed and Undirected Graphs have same result
// We need to find connected components/(Groups of connected vertices)

// 1
// 7
// 6
// 0 1
// 1 2
// 0 2
// 3 4
// 3 5
// 5 6
//
// Output:
// Group 1 : 0 1 2
// Group 2 : 3 4 5 6

void DFS(vector< vector<int> > g, int s, map<int,bool> &visited, vector<int> &group){
visited[s]=true;
group.push_back(s); // adding to stack while DFS
for(int i=0;i<g[s].size();i++){
if(visited[g[s][i]]!=true){
DFS(g,g[s][i],visited,group);
}
}
}

void ConnComp(vector< vector<int> > g){
map<int,bool> visited;
vector < vector<int> > Conn;
for(int i=0;i<g.size();i++){
if(visited[i]!=true){ // iterate for all unvisited vertices
vector<int> group;
DFS(g,i,visited,group);
}
}
for(int i=0;i<Conn.size();i++){
cout<<"Group "<<i+1<<" : ";
for(int j=0;j<Conn[i].size();j++){
cout<<Conn[i][j]<<" ";
}
cout<<endl;
}

}

int main(){
// freopen("ip.txt","r",stdin);
int t;
cin>>t;
while(t--){
int v,e;
cin>>v;
cin>>e;
vector< vector<int> > g(v);
for(int i=0;i<e;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
//g[y].push_back(x);    // in case of Undirected
}
ConnComp(g);
cout<<endl;;
}
return 0;
}
``````