This problem can be solved by finding the number of connected components when \(v\) is removed for each vertex \(v\). This can be done by the algorithm called Low Link.

Although the given graph may not be connected, we assume that it is connected. It is easy to apply it to the original problem.

Take a DFS (Depth-First Search) tree of the graph. Let \(ord_v\) be the visiting order of vertex \(v\) in the DFS, and \(low_v\) be the minimum \(ord_u\) for a vertex \(u\) that is reachable from vertex \(v\) using the edges of the DFS tree and at most one back edge. Note that all the edges of the original graph that are not used for the DFS tree are back edges.

To come to the point, the number of connected components when vertex \(v\) is removed from the graph is found as follows.

• Let \(c\) be the number of children \(w\) of \(v\) such that \(ord_v \leq low_w\).
• If \(v\) is the root, there will be \(c\) connected components.
• If \(v\) is not the root, there will be \((c+1)\) connected components.

We will prove it. As it can be shown almost similarly, we only describe the case where \(v\) is not the root. Notice that if \(v\) is the root, \(ord_v \leq low_w\) holds for all \(w\).

Let \(p\) be the parent of \(v\).

For a tree \(w\) of \(v\), if \(ord_v > low_w\), then there exists \(u\) such that \(ord_v > ord_u\) and \(u\) is reachable from \(w\) using the edges of the DFS tree and at most one back edge. Such \(u\) is an ancestor of \(p\) (or \(p\) itself), as \(ord_v > ord_u\), so removing \(v\) does not ruin the connectivity of \(u\) and \(p\); as \(u\) and \(w\) are connected, so are \(w\) and \(p\).

On the other hand, suppose that a children \(w\) satisfies \(ord_v \leq low_w\). Then the children of the subtree rooted at \(w\) are connected. If it were connected with another vertex \(u\), it would be connected with an ancestor of \(v\), which violates \(ord_v \leq low_w\). Thus, by removing \(v\) the vertices of the subtree rooted at \(w\) form a connected component.

Therefore, the proposition has been proved.