Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #define MAXN 100000
- int n, m, val, j;
- bool cycle = false;
- int clr[MAXN];
- std :: vector<int> g[MAXN];
- std :: vector <int> ans;
- void dfs (int v)
- {
- clr[v] = 1;
- for (size_t i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i];
- if (clr[to] == 0)
- dfs(to);
- else if (clr[to] == 1)
- {
- cycle = true;
- return;
- }
- }
- ans.push_back(v);
- clr[v] = 2;
- }
- void topological_sort()
- {
- ans.clear();
- for (int i = 0; i < n; ++i)
- {
- if (clr[i] == 0)
- dfs(i);
- }
- }
- int main()
- {
- std :: ifstream in ("topsort.in");
- std :: ofstream out("topsort.out");
- in >> n >> m;
- for (int i = 0; i < m; i++)
- {
- in >> j >> val;
- g[j - 1].push_back(val - 1);
- }
- topological_sort();
- if (cycle == true)
- out << "-1";
- else
- for (int i = ans.size() - 1; i >= 0; --i)
- out << ans[i] + 1 << " ";
- in.close();
- out.close();
- return 0;
- }
Add Comment
Please, Sign In to add comment