Advertisement
Guest User

Untitled

a guest
Apr 19th, 2014
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<vector>
  5. #include<algorithm>
  6. #include<queue>
  7. using namespace std;
  8. const int MX=100009;
  9. int n , m;
  10. int deg[MX] ;
  11. bool nosol=0 , vi[MX];
  12. vector<int> v[MX] , ans;
  13. priority_queue < int > Q;
  14. void relax(int x){
  15. // cout<<x<<endl;
  16. int nxt, szx=v[x].size();
  17. for(int j=0;j<szx;j++){
  18. nxt=v[x][j];
  19. if(vi[nxt]){ nosol=1; return;}
  20. deg[nxt]--;
  21. if(!deg[nxt])
  22. Q.push(-1*nxt);
  23.  
  24. }
  25. }
  26. int main(){
  27. scanf("%d %d",&n,&m);
  28. memset(deg,0,sizeof(deg));
  29. memset(vi,0,sizeof(vi));
  30. int a,b;
  31. while(m--){
  32. scanf("%d %d",&a,&b);
  33. v[a].push_back(b);
  34. deg[b]++;
  35. }
  36. for(int j=1;j<=n;j++)
  37. if(deg[j]==0) Q.push(-1*j);
  38. if(Q.size()==0) nosol=1;
  39. int node;
  40. while(!Q.empty()){
  41. node=-1*Q.top(); Q.pop();
  42. ans.push_back(node);
  43. relax(node);
  44. vi[node]=1;
  45. if(nosol) break;
  46. }
  47. if(nosol) puts("Sandro fails.");
  48. else{
  49. int szo=ans.size();
  50. for(int j=0;j<szo;j++) printf("%d ",ans[j]);
  51. if(szo) printf("%d\n",ans[ans.size()-1]);
  52. }
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement