Cod sursa(job #1425926)

Utilizator alex.bullzAlexandru Lilian alex.bullz Data 28 aprilie 2015 16:09:08
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>


struct Node {
    bool visited;
    std::vector<int> neighbors;

    Node() { 
        visited = false; 
    }
};
int g_time, scc;
std::stack<int> stack;

int min (int a, int b) { return a < b ? a : b; }
void tarjan (std::vector<Node> &graph, int index);


void dfs (std::vector<Node>& graph, int index) {
    graph[index].visited = true;
    auto neighbors = graph[index].neighbors;
    for (size_t i = 0; i < neighbors.size(); ++i) {
        if (graph[neighbors[i]].visited == false) {
            dfs (graph, neighbors[i]);
        }
    }
}

int main() {
    std::ifstream fin ("dfs.in");
    std::ofstream fout ("dfs.out");
    int m, n, source, dest;

    fin >> n;
    fin >> m;

    std::vector<Node> graph (n);
    for (int i = 0; i < m; ++i) {
        fin >> source;
        fin >> dest;
        graph[source - 1].neighbors.push_back (dest - 1);
    }

    //componenteConexe (graph);

    for (int i = 0; i < n; ++i) {
        if (graph[i].visited == false) {
            scc++;
            dfs(graph, i);
        }
    }

    fout << scc << "\n";
    return 0;
}