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).
Find all bridges using Tarjan's algorithm. For each node count number of bridges it is connected to.
If X is number of connected components at the beginning and node i is connected to b[i] bridges, then after node i is removed there will be X+b[i] components.
Theres a special case where a single node is by itself, in which case the number of connected components decreases by 1.
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.