summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2020-07-14 22:23:55 -0500
committerHaidong Ji2020-07-14 22:23:55 -0500
commit0ab896db8cff24abdf53ff49e15d8e4d6aa6ca9c (patch)
treea04bfb030b14566fcc12debe3354d747dc4fd8a7
parentce12bcff9ee1185fc7180eac5b52cdb9fa8ad5ff (diff)
Strongly Connected Components done!
-rw-r--r--Sources/GraphAlgo.cpp126
1 files changed, 72 insertions, 54 deletions
diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp
index 3da7c8d..bf0c4e3 100644
--- a/Sources/GraphAlgo.cpp
+++ b/Sources/GraphAlgo.cpp
@@ -1,11 +1,6 @@
//#include <gtest/gtest.h>
#include <iostream>
-#include <vector>
-#include <algorithm>
-
-
-#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
@@ -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) {