0
$\begingroup$

I have a graph with N nodes and M edges. It is a single component.

Now I have to delete a single node from graph, deleting that node might split graph into 1,2 or more components. The count of such components is required for each deleted node. Note that only a single node is deleted at any point of time.

I need to do this for all the nodes of the graph in a linear time.

Is this possible in linear time? I am able to do this in O(n^2) by running dfs for each node.

$\endgroup$
2
$\begingroup$

Yes, this can be done in linear time. The vertices whose removal causes the graph to split into multiple components are called articulation points. The number of such components for each vertex is the number of biconnected components that the vertex belongs to. For biconnected components and algorithms for computing them see the wikipedia page https://en.wikipedia.org/wiki/Biconnected_component.

$\endgroup$
  • $\begingroup$ how can i store count for each vertex? $\endgroup$ – user111762 Nov 8 at 14:29
  • $\begingroup$ it merely tells whether a vertex is an articulation point or not , but can i count total components which get disconnected for each articulation point !! $\endgroup$ – user111762 Nov 8 at 14:32
  • $\begingroup$ As I mentioned, the total count is the number of biconnected components that contain the vertex. $\endgroup$ – Laakeri Nov 8 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.