Cod sursa(job #2433632)

Utilizator frodobiosif aug frodob Data 28 iunie 2019 13:42:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <set>
#include <vector>

using namespace std;
vector<vector<int>> graf;
vector<int> vizitate;
int n_conexe = 0;
int N, M;
int dump() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%d  ", graf[i][j]);
        printf("\n");
    }
    return 0;
}

int dfs(int i) {
    if (vizitate[i])
        return 0;
    vizitate[i] = 1;;
    for (auto& it:graf[i]) {
        dfs(it);
    }
    return 0;
}
int main() {
    fstream fin("dfs.in", ios::in);
    fstream fout("dfs.out", ios::out);
    // citesc N M
    fin >> N >> M;
    // definesc graful
    graf.assign(N, vector<int>(0));
    vizitate.assign(N, 0);
    for (int i = 0; i < M; i++) {
        int lin, col;
        fin >> lin >> col;
        graf[lin-1].push_back(col-1);
        graf[col - 1].push_back(lin - 1);
    }
    //
    for (int i = 0; i < N; i++) {
        if (vizitate[i] == 0) {
            n_conexe++;
            dfs(i);
        }
    }
    //dump(graf, N);
    // scriu rezultatul
    fout << n_conexe;
    //cout << n_conexe << endl;
    // the end
    fin.close();
    fout.close();
    return 0;
}