Number of connected components while removing an articulation point

general
, , ,
1

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
2

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.

3

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:

4

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.
2 Likes
5

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.

6

Here’s my code:

7

No, I want the number of connected components an articulation point generates when it is removed. Initially the graph is connected.

8

:frowning: still WA.

9

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

10

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

11

your problem is actually driving me mad, and i love that. :slight_smile: as soon as i find out something, i tell you.

12

Could you please explain in detail

13

This thread is bloody 6 years old. These guys probably don’t even exist anymore. God have no one here read the definition of necroposting?

2 Likes
14

For anyone still interested in this: discrete mathematics - How to maximize the number of connected components of a graph by removing an articulation point - Mathematics Stack Exchange