Don't be trapped by the title of this problem...it would just make it more complicated I see no problem in the title. It's a very simple straight forward TOP_SORT problem. And I have seen some critical cases in other threads which cases would appear 'critical' if and only if any process other than simple top_sort is approached. I`d say don`t be trapped by the category of the problem. It says Graph Theory, but can be easily solved with other data structures. Hi! Could you please check the next test case: ``` 3 2 1 2 1 3 3 1 2 ``` result should be `no`, but 4 my case i have `yes`. Despite this i had AC. Thanks in advance! Edited by author 13.05.2020 22:47 Edited by author 13.05.2020 22:47 What is Test #16? Please someone help! What is Test #16? Please someone help! Same here... got stuck in Test16 . so why did you get the WA16? Well maybe someone gonna read this but i got WA #16 cause my logic was wrong. i thought that i need to check if i studied any of prerequisite BUT i must check if i studied ALL OF them. maybe my code would help idk #include <iostream> #include <vector> using namespace std; int N, M, a[(int)1e3 + 5], b, c; bool visited[(int)1e3 + 5], flag, ans = true; vector <vector <int> > adj((int)1e3 + 5); int main() { cin >> N >> M; while(M) cin >> b >> c, adj[c].push_back(b); for(int i = 0; i < N;++i) { cin >> a[i]; flag = true; visited[a[i]] = true; if(adj[a[i]].empty()) continue; for(int j = 0; j < adj[a[i]].size();++j) if(!visited[adj[a[i]][j]]) flag = false; if(!flag) ans = false; } if(!ans) cout <<"NO"; else cout << "YES"; } #include<bits/stdc++.h> using namespace std; int main() { long long m,i,n,a[100005][2],k,b[1005]; cin>>n>>m; for(i=0;i<m;i++){ cin>>a[i][0]>>a[i][1]; } for(i=0;i<n;i++){ cin>>k; b[k]=i; } for(i=0;i<m;i++){ if(b[a[i][0]]>b[a[i][1]]){ cout<<"NO"; return 0; } } cout<<"YES"; } 1 1 1 1 1 the answer must be "NO", not "YES" Edited by author 27.04.2007 09:34 My Program says "YES" and i got accepted I can't belive it! for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(can[i][j]) for(k=1;k<=n;k++) if(can[j][k]) can[i][k]=1; } } This test is something like this 2 2 1 2 1 2 1 2 Correct answer is YES Thank. This test help me to get AC Thank you very much,but now I've WA#33. Thank you!!! Thanks for test, i got AC Thanks a loooooooooooooooot! I think the dataset for this problem is weak. I got AC without checking for cycles. Input: 3 3 1 3 3 2 2 1 1 3 2 Correct output: NO But my code ( http://ideone.com/ZljGZ5 ) returns YES and it got Accepted. Edited by author 25.07.2017 14:17 Edited by author 25.07.2017 14:18in 1 test case we can't determine whether subject 3 should be earlier than 4 or 4 than 3, because there's isn't any edge that show which one should be sdutied ealrier, why answer is YES???? I think if we can't verify it answer should be NO Verify correctness = see if there's such a pair in the first list, that goes in reverse order on the second list. For test 2 it's pairs (3 5), (5 2), (4 2), for test 1 there's no such pairs. Who can give me some tricky tests for this problem, please! May be you need a more tricky algo? It's unable to have WA with this problem (quite simple algo) Please help, i have the same problem but i don't know where is my error here is code #include <iostream> using namespace std; int power[1005]; int deg[1005]; int mas[1005][1005]; int n,m; int answers[1006]; void input() { cin>>n>>m; int a,b; for(int i=0;i<m;i++) { cin>>a>>b; mas[a][power[a]++] = b; deg[b]++; } for(int i=0;i<n;i++) cin>>answers[i]; } void solve() { for(int i=0;i<n;i++) { if (deg[answers[i]]>0) { cout<<"NO"; return; } for(int j=0;j<power[answers[i]];j++) deg[mas[answers[i]][j]] ; } cout<<"YES"; } int main() { input(); solve(); return 0; } I don't know what are you doing, but you need just check M conditions for given sequence. I don't know what can be wrong. Edited by author 10.11.2006 04:29 Haha. I just changed int mas[1005][1005]; to int mas[1005][10005]; and get AC. I think that each limitation can occur in the input more than once i.e. some limitations can be equal :p Advice: this solution use too much memory. Really you need less than 1 Mb. Edited by author 10.11.2006 14:02 Thank you for advise. Now i just changed adjanced list stored in array to vector<vector<int> > . And my programm used only 860 Kb. Haha. I just changed int mas[1005][1005]; to int mas[1005][10005]; and get AC. I think that each limitation can occur in the input more than once i.e. some limitations can be equal :p Advice: this solution use too much memory. Really you need less than 1 Mb. Edited by author 10.11.2006 14:02 I'm very appreciate you. I used vector<vector<int> > and eventually got AC:) Thank you for the advice about limitations! You don't need to calculate the topological order. If you first calculate the topological order, and then try to "verify" the study order, will complicate a simple problem. I dont understand why i get WA # 8 It is very easy problem, i think complexity estimation 192 is overestimation. Very simple search was accepted: static bool Solve(IEnumerable<Tuple<int, int>> limitations, int[] proposedOrder) { foreach (Tuple<int, int> limitation in limitations) { int less = limitation.Item1; int greater = limitation.Item2; if (less == greater) return false; // wrong rule foreach (int currentSubj in proposedOrder) { if (currentSubj == greater) return false; // first is greater, so rule is contradicted if (currentSubj == less) break; // first is smaller, so rule is satisfied, go to next one } } return true; // all rules was satisfied } 1. Some time ago ML for it was 1MB. Try to solve within this limitation. 2. Average difficulty of a problem on Timus is ~1300, so 192 means that it is very simple problem (~15% of average difficulty), how did you get it is overestimation? for n = 10000 and m = 100000 you get approximately 2.10^6. the only way to get 0.79 is if the constant is big enough. mine is O(m + n) and I get 0.079 my algo O(m+n) too, 0.046 s O(m+n^2) algo gets AC with 0.046 :D No, I don't, idea is simple, but I have a problem: I get MLE of #15, and I can't fix it. I'we tried all ways of graph representation, but I always get MLE #15. Can someone please help me? Here is part of my code that uses the memory, the working part is eliminated: type TEdge=record i,j:integer end; var g:array[1..100001] of TEdge; st,deg:array[0..1001] of integer; sol:array[1..1000] of integer; n,m,i,k:integer; procedure sort(l,r:integer); var i,j:integer; k,t:TEdge; begin i:=l; j:=r; k:=g[(i+j) div 2]; while i<=j do begin while (g[i].i<k.i) or ((g[i].i=k.i) and (g[i].j<k.j)) do inc(i); while (k.i<g[j].i) or ((k.i=g[j].i) and (k.j<g[j].j)) do dec(j); if i<=j then begin t:=g[i]; g[i]:=g[j]; g[j]:=t; inc(i); dec(j) end end; if i<r then sort(i,r); if l<j then sort(l,j) end; begin assign(input,''); reset(input); readln(n,m); for i:=1 to n+1 do begin deg[i]:=0 end; for k:=1 to m do begin readln(g[k].i,g[k].j); inc(deg[g[k].j]) end; g[m+1].j:=0; g[m+1].i:=0; for i:=1 to n do read(sol[i]); sort(1,m); close(input); // working part goes here, cut because of fourth rule..... end. When i first time solution this problem o has WA and really don't understand WHY. But now i write a simple programm 20 lines and get AC. Sorry for my English. Edited by author 01.04.2005 20:05 Very simple... Edited by author 01.04.2005 20:08 Pls dont do any sort, just check for prerequisites of subjects in the left side of order for given subject. I think you should be able to get solution in O(N+M). I have isolated the trees at first, then i ran a topsort. I dont understand why i get WA #8 It is not topological sorting task :) I don't think, that N<=1000. Because when I submit mas[1001][1001], I get WA2. But when I submit mas[2000][2000], I get AC May be you use mas[i][j], where is i = 1001, j = 1001 or something like that My solution with mas[2000][2000] got WA 14 but with mas[3000][3000] got AC :) What is test #5. Please help! This test perhaps contain double links between vertices... 
