Cod sursa(job #2123285)

Utilizator pSergiuPatras Sergiu pSergiu Data 6 februarie 2018 00:17:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005

using namespace std;

ofstream fout("dfs.out");
vector <int> birdy[NMAX];
queue <int> q;

int n,m,nr;
bool viz[NMAX];

void input(){
    ifstream fin("dfs.in");
    fin>>n>>m;
    int a,b;
    while(fin>>a>>b){
        birdy[a].push_back(b);
        birdy[b].push_back(a);
    }
    fin.close();
}

void dfs(){
    int nod;
    while(!q.empty()){
        nod = q.front();
        q.pop();
        for(auto i : birdy[nod]){
            if(!viz[i]){
                viz[i] = true;
                q.push(i);
            }
        }
    }
}

int main()
{
    input();
    for(int i=1;i<=n;i++)
        if(!viz[i]){
            q.push(i);
            dfs();
            nr++;
        }
    fout<<nr;
    fout.close();
    return 0;
}