diff options
| -rw-r--r-- | Sources/GraphAlgo.cpp | 126 |
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) { |