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

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.