KINGCON - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Jay Pandya
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

EASY

PREREQUISITES:

Biconnected components

PROBLEM:

Getting rid of the story line the problem simply asks to find the number of articulation points in the undirected graph and multiply it by K.

EXPLANATION:

Naive approach would be for each vertex delete it from the graph and check the connectivity. Such approach has complexity O(N * M) and should get TLE. So something clever should be invented.

The problem could be solved using simple DFS in O(N + M) time. For this, some magic value low(v) is calculated for each vertex v and this allows to check whether v is articulation point in O(1) time inside DFS. The root of the DFS traversal tree should be analyzed in another way. Namely it will be an articulation point if and only if it has at least two sons in this tree.

But sincerely speaking biconnected components, articulation points and bridges is one of my unfavorite topics :slight_smile:
So I prefer to forward you to some existing tutorials for further details of the mentioned approach:

  • Exercise 23-2 in famous book “Introduction to Algorithms” by Cormen and others.
  • The article on e-maxx.ru. It seems to be very well written but unfortunately it is only in Russian. But code there is working - I’ve checked and get AC here :slight_smile: But be careful with IS_CUTPOINT(v); it could say this several times for the same vertex.
  • The article at Wikipedia. Unfortunately it contains no code snippets so it could be hard to learn this topic efficiently from there.
  • Yet another tutorial. It seems to be really good introduction to DFS and its applications with code snippets.
  • Several other tutorials: click, click, click.

Also I provide a lot of related problems on biconnected components, so don’t blame me much for not writing yet another tutorial on this topic :slight_smile:

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be provided soon.
Tester’s solution can be found here.

RELATED PROBLEMS:

UVA - 796 - Critical Links
TJU - 2840 - Apple Tree
UVA - 610 - Street Directions
UVA - 10972 - RevolC FaeLoN
PKU - 3177 - Redundant Paths
Live Archive - 4186 - Lucky cities

7 Likes
2

Thanks for the new algorithm I can learn, never met that before.

7 Likes
3

me 2… Took a lot of time to find it, at first I thought it was mostly a had hoc problem because a lot of people were solving it and good tutorials on this were hard to find…

2 Likes
4

@anton_lunyov >> thanks for related problems, really. I used to get nightmares not practicing much in Graph Algorithms, but now I will work harder.

5

Okay articulation points concept was a new thing to me. But I tried another approach:

That for each vertex(V) having more than one vertices, we apply DFS on any of its adjacent vertex and see if all other adjacent vertices can be reached through some other path except V or not. That led to TLE. Can you please tell why? It seems really time consuming, but can’t I just put some trick to run within TL? http://www.codechef.com/viewsolution/2019855

6

Such solution has complexity O(N * M). In this problem N could be up to 3000 and M could be up to 4500000. So N * M is very large number. It depends on test data whether such solution could be fit into TL using some tricks.

2 Likes
7

@bugkiller I tried the same, but it was only “are test cases weak?” test…

1 Like
8

@betlista >> Because before went to depth I wanted to first try out from things that I already know but … :frowning: rather I am thankful that I learned new things.

9

I have used the following approach :

 1. get the degree of each node in the graph.
 2. while(all nodes are not visited)
    {
        a. consider node N with maximum degree.if degree of two nodes are equal, then the one which is visited gets preference.
        b. for each of its neighbor
           {
               i.  mark the neighbor as visited.
               ii. reduce the degree of neighbor by 1.
           }
        c. mark the node N as visited.
        d. reduce the degree of N to 0.
    }
3. the number of times the above loop executes, is the required count.

Following is my attempt for this problem :

http://www.codechef.com/viewsolution/2008751

Hence or otherwise, could you explain why DFS should give the solution?

10

@avinrox: It is not just DFS. You have to do some more stuff which is explained in all the links in the editorial. Even i found it difficult to understand the extra magic that went in after we DF traversal, but later made sense after i read it multiple times. Here is my simplified understanding of it.

Assume you have a graph (for simplicity assume it is a fully connected graph, so no matter from which node we start, we end up with only 1 forest). Now imagine you take off a node from DF tree. Now by removing the node (yellow node in below image) , we have literally divided the tree in to ,many forests, one with all nodes above the deleted node and others at the children’s of the deleted node.(see image again).
![alt text][1]
Now after deleting the node, we need to find if there is any way for children nodes to find a path back to the forest#1. That is when we start adding back edges and check if there is way up to forest#1. If we see node “C” and node “D”, have a way back to forest#1 (through dotted back edge), but no such back edge exists for any of the nodes in forest#2. Hence deleting the node, will eventually lead to breaking up of a connected tree in to multiple forest and hence it (yellow node) is a articulation point.

Hope it helps :slight_smile: Please correct if i’ve misunderstood something.
[1]: http://discuss.codechef.com/upfiles/Picture2_1.png

6 Likes
11

@admin: Can you please tell me which test case gave WA for my submission (below). I am sure i missed some case.

http://www.codechef.com/viewsolution/2040555

12

If I did it correctly, than here it returns 2 and expected result is 1

13

Can anyone explain me whats wrong in my


[1] which I have written in python..... Since similar submission of mine got accepted in C++


  [1]: http://www.codechef.com/viewplaintext/2054619
14

Here I encountered the wierdest error of all times.
For one sequence of input i got correct answer for other sequence of same input i got runtime error in C++ finally i submitted in c with same idea and got AC. Articulation points was definitely new concept and worth learning thanks to codechef :slight_smile:

15

@betlista: Thanks a lot. Figured out my mistake. :slight_smile:

16

can anyone please look at http://www.codechef.com/viewplaintext/2037379. I used the same dfs approach mentioned but still I am getting a TLE. Where I am going wrong?

17

Hello, this was my first participation in a Codechef contest. When I saw this problem, I immediately recalled my Discrete Mathematics lessons and implemented an algorithm searching articulations. I believe it runs in O(n), but still I got TLE. Coud anyone please have a look at it and tell me what’s wrong? Thanks a lot. For clarification: I colored nodes that have not been opened yet as WHITE, nodes whose descendants are being searched are GREY and nodes whose all descendants have been searched are BLACK.

http://www.codechef.com/viewsolution/2052773

18

@vagrawal13: I had a look at your code, I think instead of this:

FOR(i,0,n)
    if(pre[i] == -1)
        dfs(i,i);

You can just call dfs(0,0), since in the beginning there is “unity” so the dfs(0, 0) will go through all nodes. Otherwise I didn’t notice any problem with your code. My Java code is similar and also TLE, so I hope somebody can explain this to us :slight_smile:

19

I’ve just checked a successful Java solution. I noticed the programmer used a custom fast I/O, so I modified my own solution with this fast I/O and got AC. So even using Java buffered streams is not fast enough and it is neccessary to use custom I/O. I think this should be included in the FAQ. Don’t you use Scanner, don’t you use BufferedReader, use custom I/O. It is a huge difference !!! I measured execution of 100 test cases (all of them being the example test case). When using BufferedReader + Scanner it took 0.646 seconds, when using custom I/O it just took 0.026 seconds.

@vagrawal13: I guess your problem is the same as mine, you can use eg. getInt() from @bhambya 's code, I think you will get an AC: http://www.codechef.com/viewsolution/2018093

20

I used the same dfs approach, but was getting the TLE. And I even tried using fast IO, but it did not work. Finally is modified my code to if(m == n*(n-1)/2) return 0 ,as for complete graph there are no cut nodes and it got AC. My code was in java. I still don’t understand how many milliseconds did it save!

http://www.codechef.com/viewsolution/1994713