From a80b82ef6c4214d16b5c6df76c90fb88f23329f7 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 23:04:26 +0100
Subject: Algorithms : complete 03-algorithms_on_graphs 02-decomposition

---
 .../02-decomposition/01-acyclicity/acyclicity.cpp  | 38 +++++++++++++--
 .../02-decomposition/02-toposort/toposort.cpp      | 21 ++++++--
 .../03-strongly_connected/strongly_connected.cpp   | 56 ++++++++++++++++++++--
 3 files changed, 101 insertions(+), 14 deletions(-)

diff --git a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp
index 9cd27e6..24e9371 100644
--- a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp
+++ b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp
@@ -1,12 +1,42 @@
 #include <iostream>
 #include <vector>
+#include <stack>
 
 using std::vector;
-using std::pair;
+using std::stack;
 
 int acyclic(vector<vector<int> > &adj) {
-  //write your code here
-  return 0;
+    vector<bool> marked(adj.size());
+    vector<bool> visited(adj.size());
+
+    stack<int> st;
+
+    for (int i = 0; i < adj.size(); i++) {
+        if (marked[i])
+            continue;
+        st.push(i);
+        while(!st.empty()) {
+            int v = st.top();
+            visited[v] = true;
+            int s = adj[v].size();
+            for (int j = 0; j < s; j++) {
+                int w = adj[v][j];
+                if (!marked[w]) {
+                    if (visited[w])
+                        return 1;
+                    st.push(w);
+                }
+            }
+
+            if (st.top() == v) {
+                visited[v] = false;
+                marked[v] = true;
+                st.pop();
+            }
+        }
+    }
+
+    return 0;
 }
 
 int main() {
@@ -18,5 +48,5 @@ int main() {
     std::cin >> x >> y;
     adj[x - 1].push_back(y - 1);
   }
-  std::cout << acyclic(adj);
+  std::cout << acyclic(adj) << '\n';
 }
diff --git a/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp b/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp
index bc37a24..7b45190 100644
--- a/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp
+++ b/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp
@@ -3,16 +3,26 @@
 #include <vector>
 
 using std::vector;
-using std::pair;
 
-void dfs(vector<vector<int> > &adj, vector<int> &used, vector<int> &order, int x) {
-  //write your code here
-}     
+void dfs(vector<vector<int> > &adj, vector<int> &used, vector<int> &order, int v) {
+    used[v] = true;
+    int s = adj[v].size();
+    for (int j = 0; j < s; j++) {
+        int w = adj[v][j];
+        if (!used[w])
+            dfs(adj, used, order, w);
+    }
+    order.push_back(v);
+}
 
 vector<int> toposort(vector<vector<int> > adj) {
   vector<int> used(adj.size(), 0);
   vector<int> order;
-  //write your code here
+  for (int i = 0; i < adj.size(); i++) {
+      if (!used[i])
+          dfs(adj, used, order, i);
+  }
+  std::reverse(order.begin(), order.end());
   return order;
 }
 
@@ -29,4 +39,5 @@ int main() {
   for (size_t i = 0; i < order.size(); i++) {
     std::cout << order[i] + 1 << " ";
   }
+  std::cout << '\n';
 }
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';
 }
-- 
cgit v1.1-2-g2b99