Cod sursa(job #2587679)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 23 martie 2020 13:36:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

vector < int > adiac[100005];
queue < int > q;

int n,m;
int nod1,nod2;
int nodviz[100005];
int nrconex;
int nod;

void dfs() {
    while (q.empty()==0) {
        nod=q.front();
        for (auto k=adiac[nod].begin(); k!=adiac[nod].end(); ++k) {
             if (nodviz[*k]==0) {
                q.push(*k);
             }
        }
        nodviz[nod]=1;
        q.pop();
    }
}

int main()
{
     f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> nod1 >> nod2;
        adiac[nod1].push_back(nod2);
        adiac[nod2].push_back(nod1);
    }
        for (int i=1;i<=n;i++) {
            if (nodviz[i]==0) {
                q.push(i);
                dfs();
                nrconex++;
            }
        }
     g << nrconex;
    return 0;
}