Regarding Lonely Cycles question

aug18
long-contest

#1

I am not able to find a test case where my logic goes wrong…
My submission is- My submission

My logic goes as such…
For each node x, I find in and out which are pairs… 1st index stores without cycle 2nd stores with cycle…in[x] means within the subtree of node x and also considering x… for this I merge its children’s “in” values and also some node in its subtree from which there is back-edge to x.

Out[x] position means same as above…It means the nodes we can visit in the tree except its subtree but including the node itself…for this I merge its parent’s out and also it’s siblings in…Also in case of back-edge from x to some node higher in the dfs traversal tree, I merge its out…

For answer, consider for edge (a-b)

case (i):(a is dfs_par** or vice versa… and not part of same cycle) answer is (in**)*(merge(out[a], sibling**))

case (ii):(neither is parent of other but are part of cycle connected by back-edge)answer is (in**)*(out[a])
(consider a comes before b in dfs traversal)


#2

You’ve a minor mistake while calculating paths for edges which are near two cycle.

Link to your code : https://ideone.com/8OFIAS with input and expected output, and output of your code.
For edge 7-5, the answer is 2 but your code outputs 1.


#3

Still getting WA…that was the error though