Cod sursa(job #2789902)

Utilizator Tache_RoxanaTache Roxana Tache_Roxana Data 28 octombrie 2021 09:07:38
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;

class Graf {
    vector<list<int>> noduri;
    void dfs(int nod, vector<bool> &viziate) {
        viziate[nod] = true;
        for(auto i: noduri[nod])
            if(!viziate[i])
                dfs(i, viziate);
    }
public:
    Graf(vector<list<int>> _noduri, bool _oriented=true) : noduri(_noduri) {}
    friend ostream& operator<< (ostream& os, Graf graf) {
        os << graf.noduri.size() << " nodes\n";
        for(int i = 0; i < graf.noduri.size(); i++) {
            os << "node " << i << ": ";
            for(int j: graf.noduri[i])
                os << j << " ";
            os << "\n";
        }
        return os;
    }
    int nrConexe() {
        vector<bool> viziate(noduri.size());
        int nr=0;
        for(int i = 0; i < noduri.size(); i++) {
            if(!viziate[i]) {
                dfs(i, viziate);
                nr++;
            }
        }
        return nr;
    }
};

int main() {
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    int n, m;
    in >> n >> m;
    vector<list<int>> aux(n);
    for(int i = 0; i < m; i++) {
        int x1, x2;
        in >> x1 >> x2;
        aux[x1].push_back(x2);
        aux[x2].push_back(x1);  // daca e neorientat
    }
    Graf graf(aux);
    out << graf.nrConexe();
    return 0;
}