Cod sursa(job #1129820)

Utilizator denis_tdrdenis tdr denis_tdr Data 28 februarie 2014 09:37:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#define NMax 100001
using namespace std;
int n, m, x, y, crt=0;
vector<list<int> > v;
vector<bool> cc;
list<int>::iterator it;
queue<int> coada;

void parcurgere(int x0){
    coada.push(x0);
    do{
        x0=coada.front(); coada.pop();
        cc[x0]=true;
        for(it=v[x0].begin();it!=v[x0].end();it++)
            if(!cc[*it])
                coada.push(*it);

    }while(!coada.empty());
}
int main(){
    ifstream f("dfs.in");
    f>>n>>m;
    v.resize(n+1);
    cc.resize(n+1, 0);
    while(m--)
        f>>x>>y, v[x].push_back(y), v[y].push_back(x);
    for(int i=1;i<=n;i++)
        if(!cc[i])
            parcurgere(i), crt++;
    ofstream g("dfs.out");
    g<<crt;
    return 0;
}