From 0c0188d855ca9f452b7fe44d51f86661850ca892 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:06:24 +0100
Subject: Algorithms : complete 03-algorithms_on_graphs 03-paths_in_graphs

---
 .../03-paths_in_graphs/01-bfs/bfs.cpp              | 22 +++++++++++++---
 .../03-paths_in_graphs/02-bipartite/bipartite.cpp  | 29 +++++++++++++++++++---
 2 files changed, 45 insertions(+), 6 deletions(-)

diff --git a/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp b/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp
index 5a6da4b..a411789 100644
--- a/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp
+++ b/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp
@@ -6,8 +6,24 @@ using std::vector;
 using std::queue;
 
 int distance(vector<vector<int> > &adj, int s, int t) {
-  //write your code here
-  return -1;
+  vector<int> d(adj.size(), -1);
+
+  queue<int> q;
+  q.push(s);
+  d[s] = 0;
+
+  while (!q.empty()) {
+      int v = q.front();
+      q.pop();
+      for (int i = 0; i < adj[v].size(); i++) {
+          int w = adj[v][i];
+          if (d[w] == -1) {
+              q.push(w);
+              d[w] = d[v] + 1;
+          }
+      }
+  }
+  return d[t];
 }
 
 int main() {
@@ -23,5 +39,5 @@ int main() {
   int s, t;
   std::cin >> s >> t;
   s--, t--;
-  std::cout << distance(adj, s, t);
+  std::cout << distance(adj, s, t) << '\n';
 }
diff --git a/03-algorithms_on_graphs/03-paths_in_graphs/02-bipartite/bipartite.cpp b/03-algorithms_on_graphs/03-paths_in_graphs/02-bipartite/bipartite.cpp
index f97eca5..dfd74e1 100644
--- a/03-algorithms_on_graphs/03-paths_in_graphs/02-bipartite/bipartite.cpp
+++ b/03-algorithms_on_graphs/03-paths_in_graphs/02-bipartite/bipartite.cpp
@@ -6,8 +6,31 @@ using std::vector;
 using std::queue;
 
 int bipartite(vector<vector<int> > &adj) {
-  //write your code here
-  return -1;
+  vector<int> t(adj.size(), -1);
+
+  queue<int> q;
+  q.push(0);
+  t[0] = 0;
+
+  int tag = 1;
+  while (!q.empty()) {
+      int v = q.front();
+      /* std::cout << " check : " << v << " tag " << tag << std::endl; */
+      q.pop();
+      tag = !t[v];
+      for (int i = 0; i < adj[v].size(); i++) {
+          int w = adj[v][i];
+          /* std::cout << "   " << w  << " " << t[w] << std::endl; */
+          if (t[w] == -1) {
+              q.push(w);
+              t[w] = tag;
+          } else if (t[w] != tag) {
+              /* std::cout << "   wrong " << w  << " " << t[w] << std::endl; */
+              return 0;
+          }
+      }
+  }
+  return 1;
 }
 
 int main() {
@@ -20,5 +43,5 @@ int main() {
     adj[x - 1].push_back(y - 1);
     adj[y - 1].push_back(x - 1);
   }
-  std::cout << bipartite(adj);
+  std::cout << bipartite(adj) << '\n';
 }
-- 
cgit v1.1-2-g2b99