Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<vector>
- #include<algorithm>
- #include<queue>
- using namespace std;
- const int MX=100009;
- int n , m;
- int deg[MX] ;
- bool nosol=0 , vi[MX];
- vector<int> v[MX] , ans;
- priority_queue < int > Q;
- void relax(int x){
- // cout<<x<<endl;
- int nxt, szx=v[x].size();
- for(int j=0;j<szx;j++){
- nxt=v[x][j];
- if(vi[nxt]){ nosol=1; return;}
- deg[nxt]--;
- if(!deg[nxt])
- Q.push(-1*nxt);
- }
- }
- int main(){
- scanf("%d %d",&n,&m);
- memset(deg,0,sizeof(deg));
- memset(vi,0,sizeof(vi));
- int a,b;
- while(m--){
- scanf("%d %d",&a,&b);
- v[a].push_back(b);
- deg[b]++;
- }
- for(int j=1;j<=n;j++)
- if(deg[j]==0) Q.push(-1*j);
- if(Q.size()==0) nosol=1;
- int node;
- while(!Q.empty()){
- node=-1*Q.top(); Q.pop();
- ans.push_back(node);
- relax(node);
- vi[node]=1;
- if(nosol) break;
- }
- if(nosol) puts("Sandro fails.");
- else{
- int szo=ans.size();
- for(int j=0;j<szo;j++) printf("%d ",ans[j]);
- if(szo) printf("%d\n",ans[ans.size()-1]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement