Cod sursa(job #2348120)

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

using namespace std;

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

int main() {
    ifstream in("dfs.in");
    vector<vector<int>> 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 = 0; i < n; ++i) {
        if (!vizitate[i]) {
            dfs(i, vizitate, muchii);
            ++comp;
        }
    }

    ofstream out("dfs.out");

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