You are not logged in. Please login at www.codechef.com to post your questions!

×

LONCYC - Editorial

1
6

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.

This question is marked "community wiki".

asked 13 Aug '18, 15:02

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 13 Aug '18, 16:28

admin's gravatar image

0★admin ♦♦
19.8k350498541

2

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.

(15 Aug '18, 02:25) meooow ♦6★

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

(15 Sep '18, 16:03) aryanc4036★

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?
link

answered 14 Aug '18, 00:07

shubham_raj199's gravatar image

5★shubham_raj199
621
accept rate: 0%

edited 14 Aug '18, 00:09

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) sarthakmanna6★
(14 Aug '18, 23:15) shubham_raj1995★

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

link

answered 14 Aug '18, 22:19

pant0000's gravatar image

4★pant0000
1114
accept rate: 10%

@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

sna902055's gravatar image

5★sna902055
425
accept rate: 7%

edited 15 Aug '18, 11:05

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

link

answered 15 Aug '18, 19:19

devarshi09's gravatar image

5★devarshi09
304
accept rate: 0%

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.

link

answered 13 Aug '18, 15:46

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

edited 13 Aug '18, 16:01

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

link

answered 13 Aug '18, 16:26

teja349's gravatar image

6★teja349
656
accept rate: 14%

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)

link

answered 14 Aug '18, 10:08

v1a9r9u8n's gravatar image

4★v1a9r9u8n
32
accept rate: 0%

Please anyone explain the 3 color method.

link

answered 15 Aug '18, 00:22

mike_shinoda's gravatar image

1★mike_shinoda
1
accept rate: 0%

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.

(19 Aug '18, 19:01) likecs6★

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

link

answered 19 Aug '18, 14:46

ayushanshul07's gravatar image

2★ayushanshul07
1
accept rate: 0%

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.

(19 Aug '18, 18:57) likecs6★

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

link

answered 24 Aug '18, 16:58

sparshkedia's gravatar image

5★sparshkedia
11
accept rate: 0%

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

link

answered 07 Sep '18, 12:34

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

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

link

answered 20 Sep '18, 15:58

xxxxxx312c's gravatar image

2★xxxxxx312c
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,683
×2,596
×726
×593
×196
×46
×33

question asked: 13 Aug '18, 15:02

question was seen: 3,573 times

last updated: 20 Sep '18, 15:58