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.
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.
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 !
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.
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:
No, I want the number of connected components an articulation point generates when it is removed. Initially the graph is connected.
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.
Could you please explain in detail
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?
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