Cod sursa(job #2794353)

Utilizator bianca_voicuBianca Voicu bianca_voicu Data 4 noiembrie 2021 18:17:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

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


class Graph {
private:
    int _n, _m;
    vector<int> _list[100001];
    int viz[100001];

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    void dfs(int start);

    int compConexe();

};

void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; i++) {
        f >> x >> y;
        _list[x].push_back(y);
        _list[y].push_back(x);
    }
}

void Graph::dfs(int node) {
    viz[node] = 1;
    for (int i = 0; i < _list[node].size(); i++) {
        if (!viz[_list[node][i]])
            dfs(_list[node][i]);
    }
}

int Graph::compConexe() {
    int i, nr = 0;
    for (i = 1; i <= _n; i++) {
        viz[i] = 0;
    }
    for (i = 1; i <= _n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i);
        }
    }
    return nr;
}


int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.addEdges();

    g << gr.compConexe();

    f.close();
    g.close();
    return 0;
}