Cod sursa(job #2171326)

Utilizator benjamin2205Zeic Beniamin benjamin2205 Data 15 martie 2018 11:56:29
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> listeAdiac[100005];

queue <int> nodCoada;

int n, m;

int vizitati[100005];

void citire();
//
//void dfs(int nodInitial) {
//    int nodCurent;
//    /// Pun nodul initial in coada si il marchez
//    nodCoada.push(nodInitial);
//    vizitati[nodInitial] = 1;
//
//
//    /// Cat timp coada nu e goala
//    while (!nodCoada.empty()) {
//        /// Scot nodurile din coada
//        nodCurent = nodCoada.front();
//        nodCoada.pop();
//
//        /// Procesez nodul ... daca are vecini, ii pun si pe ei in coada.
//        for (int i = 1; i <= n; ++i) {
//            if (matAdiac[nodCurent][i] == 1 && vizitati[i] == 0) {
//                nodCoada.push(i);
//                vizitati[i] = 1;
//            }
//        }
//    }
//}

void dfs2(int initial) {
    int nodCurent;

    nodCoada.push(initial);

    vizitati[initial] = 1;

    while(!nodCoada.empty()) {
        nodCurent = nodCoada.front();
        nodCoada.pop();

        for (int i = 0; i < listeAdiac[nodCurent].size(); ++i) {
            if (vizitati[listeAdiac[nodCurent][i]] == 0) {
                /// Pune in coada nodul care exista ca vecin
                nodCoada.push(listeAdiac[nodCurent][i]);

                vizitati[listeAdiac[nodCurent][i]] = 1;
            }
        }
    }
}

void citireLista();

int main()
{
    citireLista();

    int contor = 0;

    for(int i = 1; i <= n; ++i) {
        if (vizitati[i] == 0) {
            dfs2(i);
            contor++;
//            cout << i << ' ' << contor << '\n';
        }
    }

    g << contor;

    return 0;
}

void citireLista() {
    int prim;
    int secund;

    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        f >> prim >> secund;
        listeAdiac[prim].push_back(secund);
    }
}
//
//void citire() {
//    int prim;
//    int secund;
//
//    f >> n >> m;
//    for (int i = 1; i <= m; ++i) {
//        f >> prim >> secund;
//        matAdiac[prim][secund] = 1;
//    }
//}