Cod sursa(job #902366)

Utilizator TwistedFaithStanescu Jean Alexandru TwistedFaith Data 1 martie 2013 13:49:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

long int n; int h; bool s[100001];
vector <int> a[100001];

void citire()
{
    int x,y,m,i;
    fin>>n>>m;

    for(i=1;i<=m;i++) {fin>>x>>y; a[x].push_back(y); a[y].push_back(x);}
}

void dfs(int nod)
{
    vector<int>::iterator k;
    s[nod]=1;
    for(k=a[nod].begin(); k!=a[nod].end(); k++)
        if(!s[*k])
            dfs(*k);
}

int muchii()
{
   for(int i=1;i<=n;i++) if(!s[i]) {h++; dfs(i);}
   return h;
}

int main()
{
    citire();
    dfs(0);
    fout<<muchii();
}