Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- using namespace std;
- using ll = long long;
- using ld = long double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvl(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- int n,m;
- vector <vector<int>>G;
- vector <vector<int>> reG;
- const int wh = 0, gr = 1, bl = 2;
- vector <int> clr;
- vector <int> tp;
- bool paint = 0;
- int cmp_num = 0;
- vector <int> comp;
- void dfs(int v, int pr){
- clr[v] = gr;
- if (paint) comp[v] = cmp_num;
- for (int u: G[v]){
- if (u == pr) continue;
- else if (clr[u] == wh){
- dfs(u, v);
- }
- else if (clr[u] == gr){
- cout<<-1<<"\n";
- exit(0);
- }
- }
- clr[v] = bl;
- tp.push_back(v+1);
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n>>m;
- G.resize(n);
- clr.assign(n, wh);
- comp.resize(n);
- for (int i=0;i<m;++i){
- int a,b; cin>>a>>b;
- a--; b--;
- G[a].push_back(b);
- reG[b].push_back(a);
- }
- for (int i = 0;i<n;++i){
- if (clr[i] == wh){
- dfs(i, -1);
- }
- }
- reverse(tp.begin(), tp.end());
- cv(tp);
- paint = 1;
- for (int i=0;i<n;++i){
- if (clr[i] == wh){
- dfs(i, -1);
- cmp_num++;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement