I'm trying to solve this graph problem.
My idea so far is:
1.Build dfs tree.
2.Direct every span edge upwards.
3.Direct every back-edge downwards.
4.Traverse tree from the bottom (i.e. maximum level vertices).
5.Do the operation 2(instruction no. 2) described in the problem.
6.Flip the back-edges for the vertices which are at the current level(L).Move to the next level(i.e L-1)
7.Stop when we reach the root.
But This approach is using more than 700 moves of the 2nd type, which exceeds the limit.
Does anyone have a better approach?
My basic idea was choosing k end points (ensuring all components are covered) and trying to choose the largest distance from all currently chosen end points (randomly choose first point then use something like the greedy idea for k-centers for each successive point). BFS from these k points to get the distance to the closest end point for each node $$$x$$$, say $$$dist_{x}$$$. We will try to get some large set of nodes with the largest $$$dist_{x}$$$ for which some nodes haven't been processed yet such that there are no edges between any pair of them and point all edges inward for them except the one pointing their parent element. Repeat process till we reach the end point. I don't remember my exact construction to prove that this will work but I think its easy to show that for any dense layering that requires slow processing of these nodes with equal largest $$$dist_{x}$$$ and for $$$m \le 10^{5}$$$, the number of nodes is $$$\le 700$$$ in the first place so it works fine. And anyway $$$n = 10^{3}$$$ or $$$n = 10^{4}$$$ so such a construction is not possible.
Got 82.5 points in contest using this, would love to hear any better approaches.
Thanks for the help.It worked.
Actually I didn't get any idea for multi end points,so I was trying to solving the problem for 1 end point in all cases(even for K=8).Maybe for n= 104 it isn't possible to get one end point in less than 700 moves,hence I kept exceeding the limit.
Oh, that was most likely the problem then, the input doesn't guarantee that the graph is connected, just that it is always solvable for the given constraints (meaning that the cases with $$$k = 8$$$ can have upto 8 connected components.