Cod sursa(job #707477)

Utilizator freakingVlad Eu freaking Data 5 martie 2012 21:23:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
using namespace std;
#define nmax 100001

vector <int> a[nmax];
bool v[nmax];
long long n;

void dfs(int i)
{
    vector <int>::iterator it;
    v[i]=true;
    for(it=a[i].begin();it!=a[i].end();it++)
    {
        if(v[*it]==0)
        {
            n--;
            dfs(*it);
        }
    }

}

int main()
{
    long long m,i,j,k,elc;
    ifstream in("dfs.in");
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>j>>k;
        a[j].push_back(k);
        a[k].push_back(j);
    }
    elc=n;

    for(i=1;i<elc;i++)
        dfs(i);
    ofstream out("dfs.out");
    out<<n;
    in.close();
    out.close();
    return 0;
}