Number of connected components while removing an articulation point

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.

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 ! :slight_smile:

:frowning: still WA.

could you show us the new code ? (should be pretty similar, but anyway)

I have tried using blank line in several ways :frowning: . One of them is:

your problem is actually driving me mad, and i love that. :slight_smile: 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

  1. In case of the node, the number of children
  2. 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