Hi.
I tried solving TOPOSORT but after multiple attempts I am getting WA at 12th test case I guess.
Logic: I solved it using topological sort ( dfs) but with 2 variations to match the specifications.
- I sorted the vertices in all adjacency lists in decreasing order. And also my topological sort function is called from N to 1. For each vertex, the for loop in topo sort function runs in decreasing order since I already sorted the list of adjacent vertices. This ensures the printing of vertices in increasing order as I'm using a stack.
2 . For detecting a cycle and hence failure in task completion, whenever I call topological sort function on a vertex v from outisde, I mark its markerNode as v. Then when I call topo sort recursively, all unvisited vertices are visited and their markerNodes are marked as v. So, whenever I encounter a visited vertex with the same markerNode, this means that while doing topo sort for the same unit, I encountered a vertex twice, which implies there is a cycle.
I tested my program on a lot of good test cases.
1
5 3
5 1
1 2
3 4
Output - 3 4 5 1 2
2
7 4
5 1
1 2
2 3
4 6
Output - 4 5 1 2 3 6 7
3
2 2
1 2
2 1
Output - Sandro fails.
I also picked an AC implementation from stackoverflow to find the differences in both programs. Only thing I was missing was the check of number of elements pushed in stack == N which I added to my program later.
Got almost 12 WAs. Pleaseee help!!
Here is my code
http://ideone.com/xiSe3A
Also, the AC implementation which I already tested is here:
http://stackoverflow.com/a/17434144
Any help would be greatly appreciated