Cod sursa(job #1705514)

Utilizator razvan3895Razvan-Mihai Chitu razvan3895 Data 20 mai 2016 18:41:14
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>


using namespace std;

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


int n;
vector<vector<int> > edges;
bool visited[100001];

void dfs(int start) {
    visited[start] = true;

    for (unsigned i = 0; i < edges[start].size(); ++i) {
        if (!visited[edges[start][i]]) {
            dfs(edges[start][i]);
        }
    }
}


int main() {
    int m;

    in >> n >> m;

    edges.reserve(n + 1);

    for (int i = 0; i < m; ++i) {
        int x, y;

        in >> x >> y;

        edges[x].push_back(y);
    }

    int components = 0;

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

    out << components << '\n';

    return 0;
}