Cod sursa(job #454763)

Utilizator sapiensCernov Vladimir sapiens Data 12 mai 2010 14:03:24
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <vector>
#include <fstream>
using namespace std;

ifstream fin; ofstream fout;
vector <long> a[100000];
long n,m,i,k,x,y; bool b[100000];

void visit (long x) {
     vector <long>::iterator it;
     if (!b[x]) {
        b[x]=1;
        for (it=a[x].begin (); it!=a[x].end (); it++) visit (*it);
     }
}

int main () {
    fin.open ("dfs.in"); fout.open ("dfs.out");
    fin>>n>>m;
    for (i=0; i<m; i++) {
        fin>>x>>y;
        a[x].push_back (y);
        a[y].push_back (x);
    }
    for (i=1; i<=n; i++)
        if (!b[i]) {
           k++;
           visit (i);
        }
    fout<<k<<endl;
    fin.close (); fout.close ();
    return 0;
}