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 -#include -#include -#include - - #include #include #include @@ -15,69 +10,92 @@ 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) { +template +vector sort_indexes(const vector &v) { - // initialize original index locations - vector idx(v.size()); - iota(idx.begin(), idx.end(), 0); + // 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]; }); + // 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& clock, vector& postV) { - postV[v] = clock[0]; - clock[0] = clock[0] + 1; +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); - } - postVisit(v, clock, postV); + +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); + } } -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); + } + } + return adjReverse; } -vector toposort(vector > adj) { - vector visited(adj.size(), false); - vector order; - vector postV(adj.size(), 0); - vector clock(1, 0); +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); - dfs(adj, visited, postV, clock); - for (auto i : sort_indexes(postV)) { - order.push_back(i); - } - return order; + 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; } int main() { - size_t n, m; - std::cin >> n >> m; - vector > adj(n, vector()); - for (size_t i = 0; i < m; i++) { - int x, y; - std::cin >> x >> y; - adj[x - 1].push_back(y - 1); - } - vector 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 > adj(n, vector()); + 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