From 8b1d89f99eacc097d354b0f5564c6654b84510e8 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Sun, 13 Nov 2016 22:42:19 +0100 Subject: Algorithms : complete 03-algorithms_on_graphs 01-decomposition --- .../01-reachability/reachability.cpp | 29 +++++++++++++++++++--- 1 file changed, 25 insertions(+), 4 deletions(-) (limited to '03-algorithms_on_graphs/01-decomposition/01-reachability') 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 #include +#include using std::vector; +using std::stack; using std::pair; -int reach(vector > &adj, int x, int y) { - //write your code here - return 0; +int reach(vector > &adj, int x, int y) +{ + vector visited(adj.size()); + stack 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'; } -- cgit v1.2.3