1 files changed, 25 insertions, 4 deletions
diff --git a/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp b/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp
index cb2e76f..5cbccbc 100644
--- a/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp
+++ b/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp
@@ -1,13 +1,34 @@
 #include <iostream>
 #include <vector>
+#include <stack>
 
 using std::vector;
+using std::stack;
 using std::pair;
 
 
-int reach(vector<vector<int> > &adj, int x, int y) {
-  //write your code here
-  return 0;
+int reach(vector<vector<int> > &adj, int x, int y)
+{
+    vector<bool> visited(adj.size());
+    stack<int> st;
+
+    st.push(x);
+
+    while(!st.empty()) {
+        int v = st.top();
+        if (v == y)
+            return 1;
+        st.pop();
+        visited[v] = true;
+        int s = adj[v].size();
+        for (int i = 0; i < s; i++) {
+            int w = adj[v][i];
+            if (!visited[w])
+                st.push(w);
+        }
+    }
+
+    return 0;
 }
 
 int main() {
@@ -22,5 +43,5 @@ int main() {
   }
   int x, y;
   std::cin >> x >> y;
-  std::cout << reach(adj, x - 1, y - 1);
+  std::cout << reach(adj, x - 1, y - 1) << '\n';
 }