Cod sursa(job #2780156)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 6 octombrie 2021 10:44:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<vector>
using namespace std;

class Graf {
    int n;
    int m;
    vector<int> v[100002];
    bool viz[100002];
public:
    Graf(int n, int m, pair<int, int> muchii[]);
    int nrComponenteConexe();
private:
    void dfs(int nod);
};

Graf :: Graf(int n, int m, pair<int, int> muchii[]) {
    this->n = n;
    this->m = m;
    for (int i = 1; i <= m; i++) {
        v[ muchii[i].first ].push_back(muchii[i].second);
        v[ muchii[i].second ].push_back(muchii[i].first);
    }
}
int Graf :: nrComponenteConexe() {
    for (int i = 1; i <= n; i++) {
        viz[i] = false;
    }
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i);
        }
    }
    return nr;
}
void Graf :: dfs(int nod) {
    viz[nod] = true;
    for (int i = 0; i < v[nod].size(); i++) {
        if (!viz[ v[nod][i] ]) {
            dfs(v[nod][i]);
        }
    }
}

int n, m, i;
pair<int, int> muchii[200005];
ifstream fin ("dfs.in");
ofstream fout("dfs.out");
int main() {
    fin>> n >> m;
    for (i = 1; i <= m; i++) {
        fin>> muchii[i].first >> muchii[i].second;
    }
    Graf* graf = new Graf(n, m, muchii);
    fout<< graf->nrComponenteConexe();
}