summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2020-07-16 21:27:07 -0500
committerHaidong Ji2020-07-16 21:27:07 -0500
commit1aff890249dec9e6d326e4227e52a38447927a5e (patch)
treeb37bba44d4ea45ed849a4a3ba34734102e2f779b
parent0ab896db8cff24abdf53ff49e15d8e4d6aa6ca9c (diff)
Graph BFS distance done!
-rw-r--r--Sources/GraphAlgo.cpp106
1 files changed, 28 insertions, 78 deletions
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 <gtest/gtest.h>
#include <iostream>
-#include <algorithm>
#include <vector>
-#include <numeric>
+#include <queue>
using std::vector;
-using std::pair;
-using namespace std;
-
-// https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes
-template<typename T>
-vector<size_t> sort_indexes(const vector<T> &v) {
-
- // initialize original index locations
- vector<size_t> 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<vector<int>> &adj,
- vector<bool> &visited) {
- visited[v] = true;
- for (int w : adj[v]) {
- if (!visited[w])
- exploreWithoutPostV(w, adj, visited);
- }
-}
-
-void explore(int v, vector<vector<int>> &adj, vector<bool> &visited,
- vector<int> &postV, vector<int> &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<vector<int> > &adj, vector<bool> &visited, vector<int> &postV,
- vector<int> &clock) {
- for (size_t v = 0; v < adj.size(); v++) {
- if (!visited[v])
- explore(v, adj, visited, postV, clock);
- }
-}
-
-vector<vector<int>> reverseG(vector<vector<int>> &adj) {
- vector<vector<int> > adjReverse(adj.size(), vector<int>());
-
- 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<vector<int>> &adj, int s, vector<int> &dist) {
+ queue<int> 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<vector<int> > adj) {
- int result = 0;
- vector<vector<int>> adjReversal = reverseG(adj);
- vector<bool> adjReversalVisited(adj.size(), false);
- vector<int> postV(adj.size(), 0);
- vector<int> clock(1, 0);
+int distance(vector<vector<int> > &adj, int s, int t) {
+ vector<int> dist(adj.size(), -1);
+ dist[s] = 0;
- dfs(adjReversal, adjReversalVisited, postV, clock);
- vector<bool> 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<vector<int> > adj(n, vector<int>());
- 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) {