You are given an undirected graph,and a set of queries, where each query gives a vertice which is an articulation point of the graph.For each query we have to print the size of various connected components formed.
what is the question?
You can use DFS to solve this. Maintain subtree sizes in the DFS tree. Since you need to count components that will get separated when an articulation point is removed, each such component will be a child of that particular node in the DFS tree (because there will be no back edges from it going above the articulation point in the DFS tree). You just need to print the subtree sizes of all the child nodes. There will be one other component, with size = total number of nodes - (sum of all subtree sizes).
Edit : You only need to count child nodes that dont have back edges going above the vertex you are considering.
1 Like