#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define siz 1000005
vector <int> vec[siz];
vector <int> component;
bool color[siz];
int node,edge;
void reset(){
for(int i=0;i<=node;i++){
color[i]=false;
vec[i].clear();
}
}
void dfs(int n){
color[n]=true;
component.push_back(n);
for(int i=0;i<vec[n].size();i++){
int v=vec[n][i];
if(!color[v]){
dfs(v);
}
}
}
int main()
{
int u,v;
freopen("input.txt","r",stdin);
while(scanf("%d%d",&node,&edge)==2){
reset();
for(int i=0;i<edge;i++){
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
for(int i=1;i<=node;i++){
if(!color[i]){
component.clear();
dfs(i);
puts("Components");
for(int j=0;j<component.size();j++){
if(j) printf(" ");
printf("%d",component[j]);
}
printf("\n");
}
}
}
return 0;
}
Wednesday, October 31, 2012
Finding The Connected Component
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment