diff options
| -rw-r--r-- | .settings/language.settings.xml | 4 | ||||
| -rw-r--r-- | Sources/GraphAlgo.cpp | 109 |
2 files changed, 67 insertions, 46 deletions
diff --git a/.settings/language.settings.xml b/.settings/language.settings.xml index 98282f8..127216a 100644 --- a/.settings/language.settings.xml +++ b/.settings/language.settings.xml @@ -5,7 +5,7 @@ <provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/> <provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/> <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-1521639620518209686" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-1521459393963169686" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> <language-scope id="org.eclipse.cdt.core.g++"/> </provider> @@ -16,7 +16,7 @@ <provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/> <provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/> <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-1521639620518209686" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-1521459393963169686" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> <language-scope id="org.eclipse.cdt.core.g++"/> </provider> diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp index 3fdd795..3da7c8d 100644 --- a/Sources/GraphAlgo.cpp +++ b/Sources/GraphAlgo.cpp @@ -4,62 +4,83 @@ #include <vector> #include <algorithm> + +#include <iostream> +#include <algorithm> +#include <vector> +#include <numeric> + using std::vector; -//using std::pair; +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) { -void explore(vector<vector<int>> &adj, int v, vector<int> &visited, vector<int> &prev, - vector<int> &postv, vector<int> &clock) { - visited.push_back(v); - prev[v] = clock[0]; - clock[0] = clock[0] + 1; + // initialize original index locations + vector<size_t> idx(v.size()); + iota(idx.begin(), idx.end(), 0); - for (size_t i = 0; i < adj[v].size(); i++) { - if (std::find(visited.begin(), visited.end(), adj[v][i]) - == visited.end()) - explore(adj, adj[v][i], visited, prev, postv, clock); - } - postv[v] = clock[0]; - clock[0] = clock[0] + 1; + // 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 dfs(vector<vector<int>> &adj, vector<int> &visited, vector<int> &prev, - vector<int> &postv, vector<int> &clock) { - for (size_t v = 0; v < adj.size(); v++) { - if (std::find(visited.begin(), visited.end(), v) == visited.end()) - explore(adj, v, visited, prev, postv, clock); - } +void postVisit(int v, vector<int>& clock, vector<int>& postV) { + postV[v] = clock[0]; + clock[0] = clock[0] + 1; +} +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); } -int acyclic(vector<vector<int> > &adj) { - vector<int> visited; - vector<int> prev(adj.size(), 0); - vector<int> postv(adj.size(), 0); - vector<int> clock(1, 0); - dfs(adj, visited, prev, 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); + } +} - for (size_t u = 0; u < adj.size(); u++) { - for (size_t i = 0; i < adj[u].size(); i++) { - if (postv[u] <= postv[adj[u][i]]) - return 1; - } - } - return 0; +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); + + dfs(adj, visited, postV, clock); + for (auto i : sort_indexes(postV)) { + order.push_back(i); + } + return order; +} + +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 << " "; + } } //TEST(Acyclicity, ac1) { // vector<vector<int>> adj = { { 1 }, { 2 }, { 0 }, { 0 } }; // ASSERT_EQ(acyclic(adj), 1); //} - -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); - } - std::cout << acyclic(adj); -} |