Problem LinkAuthor: Noszály Áron Tester: Mark Mikhno Editorialist: Bhuvnesh Jain DifficultyMEDIUM PrerequisitesDFS, Cycle detection, case analysis. ProblemYou are given a simple graph with $N$ vertices and $M$ edges. Each vertex of the graph can belong to at most one cycle only. For every edge, you need to find the number of simple paths which contain this edge and contain at most one cycle edge in them. ExplanationThe editorial will mainly contain the case analysis through various images and will describe the approach in brief. The exact implementation details can be referred through the editorialist solution which is commented to explain the details in an editorial. The first thing to do in the problem is to first identify cycle vertices and cycle edges. This is can be simply through DFS or BFS. If you are not aware of this, I recommend you to read through it here. For detailed explanation, Cormen has a very good explanation of it using the concept of back edges and color the vertices into 3 parts white (nonvisited), gray (partiallyvisited) and black (completely visited). If you still have doubts about that, you can ask below. The sample graph which covers all possible corner cases used to describe the editorial is given below. Now, we run a DFS where we try to split the graph into various trees. The different trees are connected through edges which are part of some cycle in the graph. This means while constructing the tree we will never traverse a cycle edge. At the same time, we will root the all such trees along some vertex and also calculate the subtree size for every vertex as well. The below image shows the output of the algorithm. (This is done as part of $dfs$ function in the implementation). The root of the tree is marked in blacked colour and underlined. Now, we have 2 cases:
Consider the case for edge $(8, 9)$. Since one cycle edge is already included, it means we can only add paths which do not include cycle edges. This is exactly we tried to calculate in the DFS above. So, we basically find the number of vertices (or paths as it is a tree) for both end vertices $8$ and $9$. The answer is simply the product of these $2$ values as it means we chose endpoint from the vertex in tree same as $8$ and another end from tree same as $9$.
Consider the case for edge $(12, 15)$. We split the answer into two parts: one containing no cycle edge and other containing one cycle edge. For the first case, we simply use the DFS done before. The vertices for starting and ending parts are highlighted in different colours. The answer is simply the product of the number of ways of choosing starting and ending vertices. Now for the case when the path contains exactly one edge from a cycle, we again have 2 options. The cycle edge comes from the vertex $12$ or from vertex $15$. The first case is highlighted in the left image while the second case is highlighted in the right image. Below figures also highlight how the calculation is done for other noncycle edges like $(1, 8)$ and $(1, 3)$. Edge $(1, 8)$. Nocycle path: Cycleedge paths (Left: containing cycle as part of vertex $1$, Right: containing cycle as part of vertex $8$) Edge $(1, 3)$. Nocycle path: Cycleedge paths (Left: containing cycle as part of vertex $1$, Right: containing cycle as part of vertex $3$) The exact details of the above cases can be seen in editorialist implementation. The code is completely commented for your help and is in line with the editorial. The case analysis and what information you store in the nodes can differ and can vary across implementation as well. Feel free to share your approach, if it was somewhat different. Bonus ProblemThe problem statement doesn't provide a limit on $M$, the number of edges. Can you find the upper limit in terms of $N$? Time Complexity$O(N + M)$ per test case. Space Complexity$O(N + M)$ SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 13 Aug '18, 15:02

I guess one solution could be ,
answered 14 Aug '18, 00:07
Yes, I used the same approach. But, from where did you the log factor? Shouldn't the complexity be just O(N + M)?
(14 Aug '18, 20:47)
https://www.codechef.com/viewsolution/19722638 this causing TLE
(14 Aug '18, 23:15)

@mike_shinoda 3 color method is used for detecting all cycle in graph. Initially all vertex has color 0. start applying dfs on root and mark color of that vertex as color 1 and during dfs traversing you have to store parent of that node. during dfs traversing if next node has color 1 than you have to traversa back (using parent) to that node and mark all vertex as color 2 and give cycle number to all these vertex (In editorial solution cycle_idx++).
link
This answer is marked "community wiki".
answered 15 Aug '18, 10:51

Feeling really bad as i knew all the 3 topics and still didn't give it much thought! Time to upsolve! answered 15 Aug '18, 19:19

Maximum number of Edges, assuming Number of test cases in a file is 1, is $4996838$, which is achieved when $N = 3162$. This is derived from the form that If Number of nodes is N, Maximum number of edges allowed bounded by $min(5*10^6N, N*(N1)/2)$, which attains maximum value at N = 3162. Let me know in case of any mistake. Edit: Calculations are based on constraints of original problem. PS: It can also be proved that setting $T = 1$ only can attain above number of edges while $T>1$ cannot. answered 13 Aug '18, 15:46

@taran_1407 : I think you did not get his question correctly. M <= N1 + floor(N/3). answered 13 Aug '18, 16:26

I am not able to find a test case where my logic goes wrong... My submission issubmission 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 backedge 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 backedge from x to some node higher in the dfs traversal tree, I merge its out... For answer, consider for edge (ab) 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 backedge)answer is (in[b])*(out[a]) (consider a comes before b in dfs traversal) answered 14 Aug '18, 10:08

Can anyone explain what this line in the dfs2 function is doing? direct_cycle[u]+=direct_cycle[v]; why is this value being updated? answered 24 Aug '18, 16:58

Yeah, I have the same doubt like @sparshkedia Please can anyone answer it? @likecs answered 07 Sep '18, 12:34

Can someone please explain the dfs2 function in the editorial sol?? answered 20 Sep '18, 15:58

I think @teja349's comment below is the right answer to your bonus question but it seems to have bugged out somehow and I am unable to upvote/downvote/convert to comment/edit it.
A similar problem appeared in today's Asia Singapore Preliminary Contest.