Pagini recente » Cod sursa (job #754038) | Cod sursa (job #2173433) | Cod sursa (job #2525931) | Cod sursa (job #3238001) | Cod sursa (job #1425932)
#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) {
graph[neighbors[i]].visited = true;
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;
}