From 8b1d89f99eacc097d354b0f5564c6654b84510e8 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 22:42:19 +0100
Subject: Algorithms : complete 03-algorithms_on_graphs 01-decomposition

---
 .../01-reachability/reachability.cpp               | 29 ++++++++++++++++---
 .../connected_components.cpp                       | 33 ++++++++++++++++++----
 2 files changed, 53 insertions(+), 9 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';
 }
diff --git a/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp b/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp
index 8e6b531..d6b148b 100644
--- a/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp
+++ b/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp
@@ -1,13 +1,36 @@
 #include <iostream>
 #include <vector>
+#include <stack>
 
 using std::vector;
+using std::stack;
 using std::pair;
 
-int number_of_components(vector<vector<int> > &adj) {
-  int res = 0;
-  //write your code here
-  return res;
+int number_of_components(vector<vector<int> > &adj)
+{
+    vector<bool> visited(adj.size());
+    stack<int> st;
+
+    int cc = 0;
+    for (int j = 0; j < adj.size(); j++) {
+        if (visited[j])
+            continue;
+        cc += 1;
+        st.push(j);
+        while(!st.empty()) {
+            int v = st.top();
+            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 cc;
 }
 
 int main() {
@@ -20,5 +43,5 @@ int main() {
     adj[x - 1].push_back(y - 1);
     adj[y - 1].push_back(x - 1);
   }
-  std::cout << number_of_components(adj);
+  std::cout << number_of_components(adj) << '\n';
 }
-- 
cgit v1.1-2-g2b99