Cod sursa(job #2433020)

Utilizator frodobiosif aug frodob Data 25 iunie 2019 17:50:01
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 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 (int j = 0; j < N; j++) {
        if (graf[i][j])
            dfs(j);
    }
    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>(N, 0));
    vizitate.assign(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++) {
        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;
}