Cod sursa(job #2348128)

Utilizator gabrielmGabriel Majeri gabrielm Data 19 februarie 2019 13:32:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

using ListaVecini = vector<int>;
using ListaAdiacenta = vector<ListaVecini>;

void dfs(
    int nod, vector<bool>& vizitate,
    const ListaAdiacenta& adiacenta
) {
    vizitate[nod] = true;
    for (int i = 0; i < adiacenta[nod].size(); ++i) {
        int vecin = adiacenta[nod][i];
        if (!vizitate[vecin]) {
            dfs(vecin, vizitate, adiacenta);
        }
    }
}

int main() {
    ifstream in("dfs.in");
    ListaAdiacenta muchii;
    int n;
    in >> n;
    muchii.resize(n + 1);

    int m;
    in >> m;

    for (int i = 0; i < m; ++i) {
        int start, end;
        in >> start >> end;

        muchii[start].push_back(end);
        muchii[end].push_back(start);
    }

    in.close();

    vector<bool> vizitate;
    vizitate.resize(n);

    int comp = 0;

    for (int i = 1; i <= n; ++i) {
        if (!vizitate[i]) {
            dfs(i, vizitate, muchii);
            ++comp;
        }
    }

    ofstream out("dfs.out");

    out << comp << '\n';
}