Cod sursa(job #2782433)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 12 octombrie 2021 13:41:23
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define N 1000001

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

class Graf {
public:
    void resetViz() {
        memset(m_viz, 0, sizeof(m_viz));
    }

    void DFS(int nod) {
        m_viz[nod] = true;

        for (auto x : m_ad[nod]) {
            if (!m_viz[x]) {
                DFS(x);
            }
        }
    }

    int CompConexe() {
        resetViz();
        int nrComp = 0;

        for (int i = 1; i <= m_n; ++i) {
            if (!m_viz[i]) {
                ++nrComp;
                DFS(i);
            }
        }

        return nrComp;
    }

    Graf(int n, vector<vector<int>> &ad) : m_n(n), m_ad(ad) {
        resetViz();
    }

private:
    int m_n;
    vector<vector<int>> m_ad;
    bool m_viz[N];
};

int main() {
    vector<vector<int>> ad(N);
    int n, m, x, y;

    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;

        ad[x].push_back(y);
        ad[y].push_back(x);
    }

    Graf G(n, ad);
    fout << G.CompConexe();

    return 0;
}