Cod sursa(job #2433009)

Utilizator frodobiosif aug frodob Data 25 iunie 2019 17:36:36
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <set>
#include <vector>

using namespace std;
typedef vector<vector<int>> matrix_type;
set<int> vizitate;
int n_conexe = 0;

int dump(matrix_type& m, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%d  ", m[i][j]);
        printf("\n");
    }
    return 0;
}

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