Given a connected undirected graph consisting of N N nodes, determine how many connected components the graph will break into if each node is removed.
For example, consider a graph with the following undirected edges:
1-2, 1-3, 1-4, 4-5, 5-6, 4-6.
If we remove node 1, there will be 3 connected components. If we remove node 2, there will be 1 connected component. If we remove node 3, there will be 1 connected component. If we remove node 4, there will be 2 connected components. If we remove node 5, there will be 1 connected component. If we remove node 6, there will be 1 connected component.
Auto comment: topic has been updated by TheCreator (previous revision, new revision, compare).
I am wrong, disregard :)
Actually, you need to count the number of articulation points, not the number of bridges, you can see why by this example:
1 2
1 3
3 2
2 4
2 5
4 5
here, there isn't any bridge but by removing node 2, there gonna be two connected components
I don't know how to quickly calculate the number of connected components by removing each articulation point, still thinking about it
https://github.com/wery0/CP-library/blob/master/Graphs/Graph/Graph.cpp#L95
bro has every single graph problems as a callable function in his library, holy shit
This problem appeared in a recent Atcoder Beginner Contest, ABC334G: Christmas Color Grid 2 and ExplodingFreeze showed me an elegant way to compute this value.