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[b] or vice versa… and not part of same cycle) answer is (in[b])*(merge(out[a], sibling[b]))
case (ii):(neither is parent of other but are part of cycle connected by back-edge)answer is (in[b])*(out[a])
(consider a comes before b in dfs traversal)