I want to calculate number of connected components an articulation/cut vertex generates while removing it. I am calculating it as number of children +1 in dfs tree of the graph( for root, number of children only if cut vertex). Am I correct? If not, then what is the correct algorithm? I am getting wa repeatedly for this problem.
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1706
1 Like
your idea is basicly the correct one : meaning finding the number of connected components in an initially connected graph if we remove each time a specific articulation point. i think it would be easier to help you if we could see your submitted code.
Here’s my code:
the number of remaining points is V - 1 - (all the vertices that are ONLY connected with the vertex that you are removing).
I guess that is the thing that you are looking for.
No, I want the number of connected components an articulation point generates when it is removed. Initially the graph is connected.
I probably found something in the output section of the problem statement :
Print a blank line after the output
for each set of input.
I think that’s the part you missed ! 
still WA.
could you show us the new code ? (should be pretty similar, but anyway)
I have tried using blank line in several ways . One of them is:
your problem is actually driving me mad, and i love that. as soon as i find out something, i tell you.
Each articulation vertex would divide it into components. The number of components can be calculated by
- In case of the node, the number of children
- In case of a normal vertex,
if(low[v]>=d[u]) art=true;: The number of times this is called. For each vertex, instead of keeping a bool AP = true, try keeping a counter, initially set to 0. Answer will be AP[i] + 1 for each vertex i.
1 Like