Algorithms : complete 03-algorithms_on_graphs 02-decomposition

1 files changed, 34 insertions, 4 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';
 }