Cod sursa(job #2035336)

Utilizator zeboftwAlex Mocanu zeboftw Data 9 octombrie 2017 11:03:20
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

ifstream fin ("dfs.in");
ofstream fout("dfs.out");
const int N_MAX = 100005;

vector<int> AD[N_MAX];
bool disc[N_MAX];
int con = 0;

void dfs (int root) {
    disc[root] = 1;
    for (vector<int>::iterator it = AD[root].begin(); it != AD[root].end(); it++) {
        if (!disc[*it]) {
            dfs(*it);
        }
    }
}

int main()
{
    int n, m;

    fin >> n >> m;

    for (int i=1; i <= m; i++) {
        int from, to;
        fin >> from >> to;
        AD[from].push_back(to);
    }

    for (int i=1; i <= n; i++) {
        if (!disc[i]) {
            dfs(i);
            con++;
        }
    }

    fout << con;
    return 0;
}