Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _GLIBCXX_DEBUG
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<vector<int>> g;
- vector<int> col;
- vector<int> out_time;
- int dfs(int u){
- int res = 0;
- col[u] = 2;
- for (int x : g[u])
- {
- if (col[x] == 2){
- return res = 1;
- }
- if (col[x] == 0){
- res = dfs(x);
- }
- }
- col[u] = 1;
- return res;
- }
- void top_sort(int u){
- if (col[u]){
- return;
- }
- col[u] = 1;
- for (int x : g[u])
- {
- top_sort(x);
- }
- out_time.push_back(u);
- return;
- }
- int main(){
- int v, e;
- cin >> v >> e;
- g.resize(v + 10);
- col.resize(v + 10);
- out_time.resize(v + 10);
- fill(col.begin(), col.end(), 0);
- for(int i = 0; i < e; i++){
- int a, b;
- cin >> a >> b;
- a--;
- b--;
- g[a].push_back(b);
- }
- for (int i = 0; i < v; i++){
- if (!col[i] && dfs(i))
- {
- cout << -1 << '\n';
- return 0;
- }
- }
- fill(col.begin(), col.end(), 0);
- for (int i = 0; i < v; i++){
- if (!col[i]){
- top_sort(i);
- }
- }
- reverse(out_time.begin(), out_time.end());
- for (int i = 0; i < v; i++){
- cout << out_time[i] + 1 << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement