Cod sursa(job #563679)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 25 martie 2011 18:26:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb

#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

#define N 100001

vector < vector <int> > v(N);
int a[N];
int n,m,sol;

void dfs (int x){

    a[x]=1;
    for(vector<int>::iterator it=v[x].begin();it<v[x].end();++it)
        if(a[(*it)]==0)
            dfs((*it));

}

int main ()
{

    ifstream in ("dfs.in");
    freopen ("dfs.out","w",stdout);
    in>>n>>m;
    for(;m;--m){
        int x,y;
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    if(a[i]==0){
        ++sol;
        dfs(i);
    }
    printf("%d\n",sol);

return 0;}