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
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 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.
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? CodeChef: Practical coding for everyone
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.
@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.
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
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.
@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
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.
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!
@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 over-optimizing.The dfs approach was already optimized.
@Tester: It is my attempt for this problem - CodeChef: Practical coding for everyone .
can anyone please look at it and tell me why it getting WA (can I know the test cases for which it getting WA)
I tried to solve the prob using Articulation Point concept but , am getting TLE. CodeChef: Practical coding for everyone :->Here is my solution.
Please debug my code
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…
