From a80b82ef6c4214d16b5c6df76c90fb88f23329f7 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Sun, 13 Nov 2016 23:04:26 +0100 Subject: Algorithms : complete 03-algorithms_on_graphs 02-decomposition --- .../03-strongly_connected/strongly_connected.cpp | 56 ++++++++++++++++++++-- 1 file changed, 51 insertions(+), 5 deletions(-) (limited to '03-algorithms_on_graphs/02-decomposition/03-strongly_connected') diff --git a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp index 0ad7b62..558c597 100644 --- a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp +++ b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp @@ -1,14 +1,60 @@ #include #include #include +#include using std::vector; -using std::pair; +using std::stack; + +void dfs(vector > &adj, vector &visited, stack &order, int v) { + visited[v] = true; + int s = adj[v].size(); + for (int j = 0; j < s; j++) { + int w = adj[v][j]; + if (!visited[w]) + dfs(adj, visited, order, w); + } + order.push(v); +} + +void dfs(vector > &adj, vector &visited, int v) { + visited[v] = true; + int s = adj[v].size(); + for (int j = 0; j < s; j++) { + int w = adj[v][j]; + if (!visited[w]) + dfs(adj, visited, w); + } +} int number_of_strongly_connected_components(vector > adj) { - int result = 0; - //write your code here - return result; + int result = 0; + + vector > radj(adj.size(), vector()); + for (size_t i = 0; i < adj.size(); i++) + for (size_t j = 0; j < adj[i].size(); j++) + radj[adj[i][j]].push_back(i); + + stack order; + vector visited(radj.size(), 0); + + for (size_t i = 0; i < adj.size(); i++) + if (!visited[i]) + dfs(adj, visited, order, i); + + for (size_t i = 0; i < visited.size(); i++) + visited[i] = false; + + while(!order.empty()) { + int v = order.top(); + order.pop(); + if (!visited[v]) { + result += 1; + dfs(radj, visited, v); + } + } + + return result; } int main() { @@ -20,5 +66,5 @@ int main() { std::cin >> x >> y; adj[x - 1].push_back(y - 1); } - std::cout << number_of_strongly_connected_components(adj); + std::cout << number_of_strongly_connected_components(adj) << '\n'; } -- cgit v1.2.3