Algorithms : complete 03-algorithms_on_graphs 02-decomposition

1 files changed, 51 insertions, 5 deletions

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 <algorithm>
 #include <iostream>
 #include <vector>
+#include <stack>
 
 using std::vector;
-using std::pair;
+using std::stack;
+
+void dfs(vector<vector<int> > &adj, vector<bool> &visited, stack<int> &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<vector<int> > &adj, vector<bool> &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<vector<int> > adj) {
-  int result = 0;
-  //write your code here
-  return result;
+    int result = 0;
+
+    vector<vector<int> > radj(adj.size(), vector<int>());
+    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<int> order;
+    vector<bool> 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';
 }