PROBLEM LINK:Author: Jay Pandya DIFFICULTY:EASY PREREQUISITES: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 :)
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 :) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be provided soon. RELATED PROBLEMS:UVA  796  Critical Links
This question is marked "community wiki".
asked 15 Apr '13, 15:00

@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).
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 :) Please correct if i've misunderstood something. answered 15 Apr '13, 18:03
@admin: Can you please tell me which test case gave WA for my submission (below). I am sure i missed some case.
(15 Apr '13, 18:05)
If I did it correctly, than here it returns 2 and expected result is 1
(15 Apr '13, 18:19)
@betlista: Thanks a lot. Figured out my mistake. :)
(15 Apr '13, 19:04)

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 answered 15 Apr '13, 16:10
2
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.
(15 Apr '13, 16:14)
@betlista >> Because before went to depth I wanted to first try out from things that I already know but .... :( rather I am thankful that I learned new things.
(15 Apr '13, 16:24)

I have used the following approach :
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? answered 15 Apr '13, 16:56
Your solution is completely wrong and seems to produce wrong output for almost all official test cases.
(17 Apr '13, 13:19)

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 :) answered 15 Apr '13, 18:39

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? answered 15 Apr '13, 23:39

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. answered 16 Apr '13, 07:15

@vagrawal13: I had a look at your code, I think instead of this:
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 :) answered 16 Apr '13, 09:18

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 answered 16 Apr '13, 10:21

@milhaus : Thanks for your help but @anunay_arunav is right. Removing those test cases do save a TLE even without using fast I/O. This is sometimes really dissapointing on part of Codechef that the time limit they set is too much strict, even after getting the algorithm correct, one has to waste time on overoptimizing.The dfs approach was already optimized. answered 16 Apr '13, 12:50

@Tester: It is my attempt for this problem  http://www.codechef.com/viewsolution/2056304 . can anyone please look at it and tell me why it getting WA (can I know the test cases for which it getting WA) answered 17 Apr '13, 12:07

Can anyone please tell me why my submission (below) gives WA. http://www.codechef.com/viewsolution/4438627 answered 02 Aug '14, 12:17

This article explains the algorithm for finding articulation points very well. It has got code too. http://www.geeksforgeeks.org/articulationpointsorcutverticesinagraph/ answered 31 Dec '14, 16:30

Can anyone have a look at my code ? http://p.ip.fi/RMG1 its giving me TLE and i m not able to figure out why.Thanks in advance:) answered 09 Jan '18, 16:44

I tried to solve the prob using Articulation Point concept but , am getting TLE. https://www.codechef.com/viewsolution/22527020 :>Here is my solution. Please debug my code answered 18 Jan, 20:21

https://www.codechef.com/viewsolution/22661232 Trick to solve this question in python:
answered 27 Jan, 14:42

@anton_lunyov >> thanks for related problems, really. I used to get nightmares not practicing much in Graph Algorithms, but now I will work harder.
Is this problem the same as the "minimum vertex cover" problem?
@tyrant No. Serf Wikipedia.
@anton_lunyov How to check whether root is an articulation point or not?