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 <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) {
-- 
cgit v1.2.3