Wednesday, October 31, 2012

Finding The Connected Component

#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;
}

No comments:

Post a Comment