Cod sursa(job #1394505)

Utilizator andytosaAndrei Tosa andytosa Data 20 martie 2015 12:57:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <queue>
#include <vector>

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

int n,m,frec[100010],i,j,a,b,lung,dest,nr;
vector<int> v[100010];
queue<int> coada;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;++i)
        if(frec[i] == 0){
            ++nr;
            frec[i]=nr;
            coada.push(i);
            while(!coada.empty()){
                a=coada.front();
                coada.pop();
                lung=v[a].size();
                for(j=0;j<lung;++j){
                    dest = v[a][j];
                    if(frec[dest] == 0){
                        frec[dest]=nr;
                        coada.push( dest );
                    }
                }
            }
        }
    fout<<nr;
    return 0;
}