From 0ab896db8cff24abdf53ff49e15d8e4d6aa6ca9c Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 14 Jul 2020 22:23:55 -0500
Subject: Strongly Connected Components done!

---
 Sources/GraphAlgo.cpp | 126 ++++++++++++++++++++++++++++----------------------
 1 file changed, 72 insertions(+), 54 deletions(-)

(limited to 'Sources')

diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp
index 3da7c8d..bf0c4e3 100644
--- a/Sources/GraphAlgo.cpp
+++ b/Sources/GraphAlgo.cpp
@@ -1,10 +1,5 @@
 //#include <gtest/gtest.h>
 
-#include <iostream>
-#include <vector>
-#include <algorithm>
-
-
 #include <iostream>
 #include <algorithm>
 #include <vector>
@@ -15,69 +10,92 @@ 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) {
+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);
+	// 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]; });
+	// 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;
+	return idx;
 }
 
-void postVisit(int v, vector<int>& clock, vector<int>& postV) {
-    postV[v] = clock[0];
-    clock[0] = clock[0] + 1;
+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);
-    }
-    postVisit(v, clock, postV);
+
+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);
+	}
 }
 
-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);
+		}
+	}
+	return adjReverse;
 }
 
-vector<int> toposort(vector<vector<int> > adj) {
-    vector<bool> visited(adj.size(), false);
-    vector<int> order;
-    vector<int> postV(adj.size(), 0);
-    vector<int> clock(1, 0);
+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);
 
-    dfs(adj, visited, postV, clock);
-    for (auto i : sort_indexes(postV)) {
-        order.push_back(i);
-    }
-    return order;
+	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;
 }
 
 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);
-    }
-    vector<int> order = toposort(adj);
-    for (size_t i = 0; i < order.size(); i++) {
-        std::cout << order[i] + 1 << " ";
-    }
+	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);
+	}
+	std::cout << number_of_strongly_connected_components(adj);
 }
 
 //TEST(Acyclicity, ac1) {
-- 
cgit v1.2.3