From 1aff890249dec9e6d326e4227e52a38447927a5e Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Thu, 16 Jul 2020 21:27:07 -0500 Subject: Graph BFS distance done! --- Sources/GraphAlgo.cpp | 106 +++++++++++++------------------------------------- 1 file changed, 28 insertions(+), 78 deletions(-) (limited to 'Sources') diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp index bf0c4e3..7385763 100644 --- a/Sources/GraphAlgo.cpp +++ b/Sources/GraphAlgo.cpp @@ -1,101 +1,51 @@ //#include #include -#include #include -#include +#include using std::vector; -using std::pair; -using namespace std; - -// https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes -template -vector sort_indexes(const vector &v) { - - // initialize original index locations - vector idx(v.size()); - iota(idx.begin(), idx.end(), 0); - - // sort indexes based on comparing values in v - // using std::stable_sort instead of std::sort - // to avoid unnecessary index re-orderings - // when v contains elements of equal values - stable_sort(idx.begin(), idx.end(), [&v](size_t i1, size_t i2) { - return v[i1] > v[i2]; - }); - - return idx; -} - -void exploreWithoutPostV(int v, vector> &adj, - vector &visited) { - visited[v] = true; - for (int w : adj[v]) { - if (!visited[w]) - exploreWithoutPostV(w, adj, visited); - } -} - -void explore(int v, vector> &adj, vector &visited, - vector &postV, vector &clock) { - visited[v] = true; - for (int w : adj[v]) { - if (!visited[w]) - explore(w, adj, visited, postV, clock); - } - postV[v] = clock[0]; - clock[0] = clock[0] + 1; -} - -void dfs(vector > &adj, vector &visited, vector &postV, - vector &clock) { - for (size_t v = 0; v < adj.size(); v++) { - if (!visited[v]) - explore(v, adj, visited, postV, clock); - } -} - -vector> reverseG(vector> &adj) { - vector > adjReverse(adj.size(), vector()); - - for (size_t v = 0; v < adj.size(); v++) { - for (int w : adj[v]) { - adjReverse[w].push_back(v); +using std::queue; + +void bfs(vector> &adj, int s, vector &dist) { + queue vertexQ; + vertexQ.push(s); + + while (!vertexQ.empty()) { + int u = vertexQ.front(); + vertexQ.pop(); + for (int i : adj[u]) { + if (dist[i] == -1) { + vertexQ.push(i); + dist[i] = dist[u] + 1; + } } } - return adjReverse; } -int number_of_strongly_connected_components(vector > adj) { - int result = 0; - vector> adjReversal = reverseG(adj); - vector adjReversalVisited(adj.size(), false); - vector postV(adj.size(), 0); - vector clock(1, 0); +int distance(vector > &adj, int s, int t) { + vector dist(adj.size(), -1); + dist[s] = 0; - dfs(adjReversal, adjReversalVisited, postV, clock); - vector visited(adj.size(), false); - for (auto i : sort_indexes(postV)) { - if (!visited[i]) { - exploreWithoutPostV(i, adj, visited); - result++; - } - } - //write your code here - return result; + bfs(adj, s, dist); + + return dist[t]; } int main() { - size_t n, m; + int n, m; std::cin >> n >> m; vector > adj(n, vector()); - for (size_t i = 0; i < m; i++) { + for (int 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); } - std::cout << number_of_strongly_connected_components(adj); + int s, t; + std::cin >> s >> t; + s--, t--; + std::cout << distance(adj, s, t); } //TEST(Acyclicity, ac1) { -- cgit v1.2.3