diff options
| -rw-r--r-- | Sources/GraphAlgo.cpp | 70 |
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); +} |