Cod sursa(job #2541922)

Utilizator KPP17Popescu Paul KPP17 Data 9 februarie 2020 09:55:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
using namespace std;



#define fisier "dfs"

#ifdef fisier
    #include <fstream>
    ifstream in(fisier ".in");
    ofstream out(fisier ".out");
#else
    #include <iostream>
    #define in cin
    #define out cout
#endif



const int
MAX_N = 100000;

int coada[MAX_N], baza, varf, n;

bool explorat[MAX_N];

#include <vector>
vector<int> de_la[MAX_N];



void add_in_coada(int nod) {

    if (!explorat[nod]) {

        coada[varf++] = nod;
        explorat[nod] = true;

    }

}



void bfs(int nod_sursa) {

    add_in_coada(nod_sursa);

    for (; baza < varf; baza++) {

        for (
            vector<int>::iterator vecin = de_la[coada[baza]].begin();
            vecin != de_la[coada[baza]].end();
            vecin++
        ) {

            //out << coada[baza] << " --> " << *vecin << endl;

            add_in_coada(*vecin);

        }

    }

}



int componente_conexe() {

    int cmp_cnx = 0;

    for (int nod = 0; nod < n; nod++) {

        if (!explorat[nod]) {

            cmp_cnx++;

            bfs(nod);

        }

    }

    return cmp_cnx;

}



int main() {

    int m, x, y;

    in >> n >> m;

    while (m--) {

        in >> x >> y;
        x--; y--;

        de_la[x].push_back(y);
        de_la[y].push_back(x);

    }

    out << componente_conexe();

}
















//