Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #include <iostream>
- #include <map>
- #include <vector>
- #include <deque>
- #include <algorithm>
- #include <bitset>
- #include <cstring>
- #include <math.h>
- #include <string>
- #include <set>
- #include <iomanip>
- #include <bitset>
- #include <random>
- #include <complex>
- #include <random>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- #define pb push_back
- #define ll long long
- #define mp make_pair
- #define fdeg firdeg
- #define snd second
- #define ins insert
- #define ld long double
- #define mt make_tuple
- #define fst first
- const double PI = acos(-1);
- // = 5e5 + 17;
- ll MOD = 1e9 + 7;
- const int INF = 1e9;
- const int MaXN = 105;
- const int N = 1e6 + 1000;
- const int maxlog = 18;
- ld ecr = 1e-8;
- vector<int> g[N];
- vector<int> topsort;
- bool used[N];
- int cl[N];
- int start , c_end;
- bool has_cycle (int u)
- {
- cl[u] = 1;
- for (auto v: g[u])
- {
- if (!cl[v])
- {
- if (has_cycle(v))
- {
- return true;
- }
- }
- else if (cl[v] == 1)
- {
- start = u;
- c_end = v;
- return true;
- }
- }
- cl[u] = 2;
- return false;
- }
- void dfs(int u)
- {
- used[u] = 1;
- for(auto v : g[u])
- {
- if(!used[v]) dfs(v);
- }
- topsort.pb(u);
- }
- signed main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n , m;
- cin >> n >> m;
- start = INF;
- for(int i = 0; i < m; i++)
- {
- int u , v;
- cin >> u >> v;
- u--, v--;
- g[u].pb(v);
- }
- for (int i = 0; i < n; i++)
- {
- if (has_cycle(i))
- {
- break;
- }
- }
- if(start < INF)
- {
- cout << -1 << "\n";
- return 0;
- }
- for(int i = 0; i < n; i++)
- {
- if(!used[i])
- {
- dfs(i);
- }
- }
- reverse(topsort.begin(), topsort.end());
- for(auto u : topsort)
- {
- cout << u + 1 << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement