Can someone please let me know what is wrong in my
[2]. Basically, what I did was, first I deleted all those vertices which don't have an edge to any other vertices (labeled as the vector **freed** in the code). I maintained two vector arrays, one for the children and other for the parent of a vertex. Initially, for the already free vertices, I removed them from their parents' adjacency list and checked if any node got free of all its children nodes, if yes, push it into the stack, make it the next to be deleted and repeat the same process till all vertices are deleted. I grouped the 1st two elements of the stack (if there were >=2 elements at a time in it) to be deleted together (because since they are in the stack, that implies they don't have any children nodes), or left a solitary 1 node to be deleted alone(in case only 1 element was left in the stack).
I tried with several possible DAGs, solved the sequence for them with hand and matched with the output of my code. Everything was right, but I still got WA. If someone could kindly find any case which I might have missed out, it would be really thankful.
Edit : [@vijju123][3] can you please close this question. Reason: Question answered, need to learn Topological sort :p
[1]: https://www.codechef.com/DEC18A/problems/DLDAG/
[2]: https://www.codechef.com/viewsolution/21984454
[3]: https://discuss.codechef.com/users/187411/vijju123
Actually in your code , you are selecting any random leaf node and starting your dfs from that node. But according to the question you have to minimize the number of steps. And your solution does not guarantee that nodes would be removed optimally.
According to the question , nodes which are at the farthest and is a leaf node should be removed first. So in my solution , I kind of calculated distance of all nodes from all leaf nodes and removed nodes which are at the farthest distance.
In my solution Here
I stored indegrees and outdegrees of each vertex and used Kahn topological sort.
Then, I started at the end of the topological sort and tried removing vertices with outdegree 0 in pairs, and if not possible, remove only one (There is always one vertex with outdegree 0).
After removing, you decrement the outdegree of each removed vertices parent…
This will create other vertices with outdegree 0 to be removed in the next step…
The vertices with outdegree 0 won’t necessarily be at the end, so the topological sort is important to reduce the overall complexity, which otherwise would be quadratic.
Okay, now I understood what the question asked. Initially, I thought that the question being Challenge should give AC for any number of steps provided they are in proper order, hence started at any node, and to my sad luck, the examples I took worked too for the same logic. Will try again. Thanks for the help.
@kshitij_07 I used the same approach initially. I also misunderstood the question. But, finally did something with topological sort and got a few points.
