fork download
copy 
  1. // TOPOSORT by muoii
  2. // https://v...content-available-to-author-only...j.com/problems/NKLEAGUE/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "main"
  6. #define maxn 1007
  7. #define oo 1000000007LL
  8. #define mid ((l+r)>>1)
  9. #define getbit(x,i) ((x)>>(i)&1)
  10. #define onbit(x,i) ((x)|(1<<(i)))
  11. #define offbit(x,i) ((x)&~(1<<(i)))
  12. #define cntbit(x) (__builtin_popcountll(x))
  13. #define meset(a,x) memset(a,x,sizeof(a))
  14. #define forinc(i,a,b) for(int i=a;i<=b;i++)
  15. #define fordec(i,a,b) for(int i=a;i>=b;i--)
  16. #define debug(x) cerr<<#x<<" = "<<x<<"\n"
  17. #define runtime(stime) ((clock() - stime) / CLOCKS_PER_SEC * 1000)
  18. #define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
  19. template<typename T> inline void inp(T &x) { static char k; static bool neg; while((k=getchar())!='-' && !isdigit(k)); neg = k=='-'; x=(neg=k=='-')?0:k-48; while(isdigit(k=getchar())) x = (x<<3) + (x<<1) +  k-48; x=neg?-x:+x; }
  20. template<typename T> inline void out(T x) { if(x<0) putchar('-'),x=-x; if(x>9) out(x/10); putchar(x%10+48); }
  21. #define space putchar(' ')
  22. #define endline putchar('\n')
  23. #define inpint ({ int x; inp(x); x; })
  24. #define inpchar ({ char k; while((k=getchar())==' ' || k=='\n'); k; })
  25. #define inpstr ({ char k; while((k=getchar())==' ' || k=='\n'); string s=""; s+=k; while((k=getchar())!=' ' && k!='\n') s+=k; s; })
  26.  
  27. /// --------------------------------------------------------------------------------------------------------------------------------
  28. #define long long long
  29. long n,m;
  30. vector<int> adj[maxn];
  31. int numbering;
  32. int num[maxn],pos[maxn];
  33. bool dd[maxn];
  34. int f[maxn];
  35. int trace[maxn];
  36.  
  37. void dfs(int u) {
  38.     if(dd[u]) return;
  39.  
  40.     dd[u] = 1;
  41.  
  42.     for(int v : adj[u]) dfs(v);
  43.  
  44.     num[u] = numbering;
  45.     pos[numbering] = u;
  46.     --numbering;
  47. }
  48.  
  49. bool topo_sort() {
  50.     bool ans = 1;
  51.  
  52.     numbering = n;
  53.  
  54.     forinc(i,1,n) dfs(i);
  55.  
  56.     return ans;
  57. }
  58. void enter(){
  59.     cin>>n;
  60.  
  61.     char x;
  62.  
  63.     forinc(i,1,n)
  64.         forinc(j,1,n) {
  65.             cin>>x;
  66.             if(x=='1') adj[i].push_back(j);
  67.         }
  68. }
  69.  
  70. void solve(){
  71.     topo_sort();
  72.  
  73.     f[n]=1;
  74.     fordec(i,n-1,1) {
  75.         int u = pos[i];
  76.  
  77.         for(int v : adj[u]) {
  78.             int j = num[v];
  79.             if(f[i]<f[j]+1) {
  80.                 f[i]=f[j]+1;
  81.                 trace[i]=j;
  82.             }
  83.         }
  84.     }
  85.  
  86.     int res = 1;
  87.     forinc(i,1,n) if(f[i]>f[res]) res=i;
  88.  
  89.     if(f[res]<n) cout<<-1;
  90.     else for(int i=res,v=pos[i];v>0;i=trace[i],v=pos[i]) cout<<v<<" ";
  91. }
  92.  
  93. int32_t main()
  94. {
  95.     checkfile(tag);
  96.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  97.  
  98.     enter();
  99.     solve();
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 5656KB
comments (?)
stdin
copy 
3
010
000
110
stdout
copy 
3 1 2
https://ideone.com/gYscjb
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!