Cod sursa(job #2030130)

Utilizator osiaccrCristian Osiac osiaccr Data 1 octombrie 2017 10:10:40
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>
#define DEF 100001

using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

int n, m, viz[DEF], sol;

vector <int> N[DEF];

void dfs (int nod) {
    viz[nod] = 1;
    for (int i = 0; i < N[nod].size (); i++) {
        if (viz[N[nod][i]] == 0) {
            dfs (N[nod][i]);
        }
    }
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        N[x].push_back (y);
    }

    for (int i = 1; i <= n; i++) {
        if (viz[i] == 0) {
            dfs (i);
            sol++;
        }
    }

    fout << sol;

    return 0;
}