LONCYC - Editorial

editorial
, , , , , ,
1

Problem Link

Practice

Contest

Author: Noszály Áron

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

DFS, Cycle detection, case analysis.

Problem

You 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.

Explanation

The 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 (non-visited), gray (partially-visited) 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:

  • CYCLE EDGE

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.

  • NON-CYCLE_EDGE

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 non-cycle edges like (1, 8) and (1, 3).

Edge (1, 8). No-cycle path:

Cycle-edge paths (Left: containing cycle as part of vertex 1, Right: containing cycle as part of vertex 8)

Edge (1, 3). No-cycle path:

Cycle-edge 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 Problem

The 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.

4 Likes
2

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^6-N, N*(N-1)/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.

3

@taran_1407 : I think you did not get his question correctly.

M <= N-1 + floor(N/3).

My thoughts towards it.

Graph must be connected with maximum cycles. To get maximum cycles each cycle will have 3 vertices. so every 3 vertices contribute one extra edge to the tree.

4

I guess one solution could be ,

  1. Find all cycles and mark all the edges that contained by some cycle as special edge.
  2. For each edge (u,v)
    i) if Special, find number of simple paths of non-special edges (u as parent) from v say P_{v} and then (v
    as a parent) from u say P_{u}.Then ans is (P_{u}+1)*(P_{v}+1).
    ii)Otherwise find number of simple paths that contains at most one special edge (P_{us} and P_{vs} ) and also ones who do not have
    special edges at all (P_{u} and P_{v} ). Now answer will be (P_{u}+1)*(P_{v}+1)+(P_{us}+1)*P_{v}+(P_{vs}+1)*P_{u}
    It can be optimized by using DP for each edge , but complexity would be around O(2*(M+N)*log(M)) and I think it will not pass, will it?
2 Likes
5

I am not able to find a test case where my logic goes wrong… My submission is-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)

6

Yes, I used the same approach. But, from where did you the log factor? Shouldn’t the complexity be just O(N + M)?

7

@likecs - Nicely explained and code is also well-commented. Good job bro…

1 Like
8

https://www.codechef.com/viewsolution/19722638 this causing TLE

9

Please anyone explain the 3 color method.

10

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.

2 Likes
11

@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++).

1 Like
12

Feeling really bad as i knew all the 3 topics and still didn’t give it much thought! Time to upsolve!

1 Like
13

Can anyone explain direct_cycle and total_cycle part in Editor’s solution(last dfs)?

14

total_cycle means all the paths having a cycle edge from any vertex in the tree found in dfs1. See this value is added to tree_root during the initial calculation, so all nodes in that tree have the same value. direct_cycle refers to cycle edges directly passing through that vertex. See that during initialisation, we only add this to the particular vertex. For details, run the code on the graph in the editorial to understand all possible cases.

15

White (or 0) means the vertex is still not visited. Black (or 2) means vertex is fully visited, meaning all vertices directly attached to it have been traversed (see when in dfs we mark such vertex). Gray (or 1) means vertex is partially visited. We can only visit an already seen node wither from a completely new vertex i.e. white or from a partially seen vertex i.e. gray. Try to run the above algorithm in the graph mentioned in the editorial to be more clear about it. Also, refer to the MIT pdf I shared.

16

Can anyone explain what this line in the dfs2 function is doing?
direct_cycle[u]+=direct_cycle[v];
why is this value being updated?

17

Yeah, I have the same doubt like @sparshkedia Please can anyone answer it? @likecs

18

A similar problem appeared in today’s Asia Singapore Preliminary Contest.

19

Can someone please explain the dfs2 function in the editorial sol??