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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ how can i store count for each vertex? $\endgroup$
    – user111762
    Commented Nov 8, 2019 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
    Commented Nov 8, 2019 at 14:32
  • $\begingroup$ As I mentioned, the total count is the number of biconnected components that contain the vertex. $\endgroup$
    – Laakeri
    Commented Nov 8, 2019 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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