summaryrefslogtreecommitdiff
path: root/Sources
diff options
context:
space:
mode:
authorHaidong Ji2020-05-10 16:21:18 -0500
committerHaidong Ji2020-05-10 16:21:18 -0500
commit0d2813a19dd37665102319bfe746b8975a080cef (patch)
treed9b3c5724aad9aaf88abd46c00356168d30cb8b3 /Sources
parentf13dfb8c438c3c565ed4ede430e6046f54e5c9d5 (diff)
Reachability C++ version done. It's not too bad after Java version isex1/FindMazeExit
done. Getting googletests up and running, and re-learn C++ contains method and looping is interesting.
Diffstat (limited to 'Sources')
-rw-r--r--Sources/GraphAlgo.cpp70
1 files 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);
+}