Cod sursa(job #2199214)

Utilizator benjamin2205Zeic Beniamin benjamin2205 Data 26 aprilie 2018 21:44:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> adiac[100005];
stack <int> coada;
int vizitati[100005];
int nNoduri, nMuchii;
int componente;

void citire();

void rezolvare(int nod) {
//    cout << "apelare" << '\n';

    coada.push(nod);
    vizitati[nod] = 1;

    while (!coada.empty()) {
        nod = coada.top();
        coada.pop();
        vizitati[nod] = 1;

        for (int i = 0; i < adiac[nod].size(); ++i) {
//            cout << nodCurent << ' ' << i << '\n';
            if (vizitati[adiac[nod][i]] == 0) {
                coada.push(adiac[nod][i]);
                vizitati[adiac[nod][i]] = 1;
            }
        }
    }

}

int main()
{
    citire();
    for (int i = 1; i <= nNoduri; ++i) {
        if (vizitati[i] == 0) {
            ++componente;
            rezolvare(i);
        }
    }

    g << componente;

    return 0;
}

void citire() {
    int prim, sec;

    f >> nNoduri >> nMuchii;

    for (int i = 1; i <= nMuchii; ++i) {
        f >> prim >> sec;
        adiac[prim].push_back(sec);
        adiac[sec].push_back(prim);
    }
}