From 0d2813a19dd37665102319bfe746b8975a080cef Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 10 May 2020 16:21:18 -0500
Subject: Reachability C++ version done. It's not too bad after Java version is
 done. Getting googletests up and running, and re-learn C++ contains method
 and looping is interesting.

---
 Sources/GraphAlgo.cpp | 70 ++++++++++++++++++++++++++-------------------------
 1 file changed, 36 insertions(+), 34 deletions(-)

diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp
index d04987f..8836b2f 100644
--- a/Sources/GraphAlgo.cpp
+++ b/Sources/GraphAlgo.cpp
@@ -1,47 +1,49 @@
+//#include <gtest/gtest.h>
+
 #include <iostream>
 #include <vector>
 #include <algorithm>
-#include <gtest/gtest.h>
 
 using std::vector;
+using std::pair;
 
-static long getMaxDotProduct(vector<int> a, vector<int> b) {
-	std::sort(a.begin(), a.end());
-	std::sort(b.begin(), b.end());
-	long result = 0;
-	for (int i = 0; i < b.size(); i++) {
-		result = (long) a[i]*b[i]+result;
+void explore(vector<vector<int>> &adj, vector<int> &visited, int x, int y) {
+	visited.push_back(x);
+	if (x == y)
+		return;
+	for (size_t i = 0; i < adj[x].size(); i++) {
+		if (std::find(visited.begin(), visited.end(), adj[x][i])
+				== visited.end())
+			explore(adj, visited, adj[x][i], y);
 	}
-	return result;
 }
 
-TEST(MaxDotProduct, Max1) {
-	vector<int> a = { 60, 100, 120 };
-	vector<int> b = { 20, 50, 30 };
-	ASSERT_EQ(getMaxDotProduct(a, b), 10200);
+int reach(vector<vector<int> > &adj, int x, int y) {
+	vector<int> visited;
+	if (x == y)
+		return 1;
+	explore(adj, visited, x, y);
+	if (std::find(visited.begin(), visited.end(), y) != visited.end())
+		return 1;
+	return 0;
 }
 
-//TEST(MaxDotProduct, Max2) {
-//	vector<int> a = { 23 };
-//	vector<int> b = { 39 };
-//	ASSERT_EQ(getMaxDotProduct(a, b), 897);
-//}
-//
-//TEST(MaxDotProduct, Max3) {
-//	vector<int> a = { 1,3,-5 };
-//	vector<int> b = { -2,4,1 };
-//	ASSERT_EQ(getMaxDotProduct(a, b), 23);
+//TEST(Reachable, Reach1) {
+//	vector<vector<int>> adj = { { 1, 3 }, { }, { 1 }, { 2 } };
+//	ASSERT_EQ(reach(adj, 0, 3), 1);
 //}
 
-//int main() {
-//  size_t n;
-//  std::cin >> n;
-//  vector<int> a(n), b(n);
-//  for (size_t i = 0; i < n; i++) {
-//    std::cin >> a[i];
-//  }
-//  for (size_t i = 0; i < n; i++) {
-//    std::cin >> b[i];
-//  }
-//  std::cout << getMaxDotProduct(a, b) << std::endl;
-//}
+int main() {
+  size_t n, m;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  for (size_t i = 0; i < m; i++) {
+    int x, y;
+    std::cin >> x >> y;
+    adj[x - 1].push_back(y - 1);
+    adj[y - 1].push_back(x - 1);
+  }
+  int x, y;
+  std::cin >> x >> y;
+  std::cout << reach(adj, x - 1, y - 1);
+}
-- 
cgit v1.2.3