I don't quite understand the problem statement.

• Is the graph directed or undirected?
• What do you mean by "picking" an articulation point?

I suppose you mean removing an articulation point, thus dividing a component into two or more components, and finding the sizes of those new components?

To find articulation points, you can do a DFS. The algorithm is as follows...

1) Do a DFS starting from an arbitrary node (say node 1)

2) Number the nodes as you visit them with DFS (Num[i])

3) Let Low[i] be the least numbered node in the DFS subtree rooted at i or connected to a node in that subtree by a back edge

Then, if L[i] >= Num[i], the node is an articulation point.

Finally, what I'd do, since there are at most 10^4 vertices, for every articulation point, do a DFS and recalculate the size of the components (DFS takes N steps to complete), so the overall complexity of the algorithm is O(N^2), which is fairly reasonable for N = 10^4.

In fact, you don't even need to do a DFS everytime you remove an articulation point. In the first DFS you do to identify articulation points, you can keep a list subsizes[i], which stores the sizes of the sub-components you would get when you remove node i. The way to do that is...

• You have a variable dfsNum, which keeps the number of nodes visited so far by the DFS
• When you recursively call DFS(k), with k being a child of i, you make prevNum = dfsNum (you keep track of the number of nodes visited before entering node k), and when the function returns, the size of the sub-component will be dfsNum — prevNum. That is, the size of that branch of the DFS subtree rooted at i.

The pseudo-code for that part would be something like this...

DFS(n, &dfsNum)
{
    minTouch = dfsNum
    Num[n] = dfsNum

    for(every child k of n)
    {
        if(!visited(n))
        {
            prevNum = dfsNum
            first = DFS(k, dfsNum + 1)
            if(first > Num[n])
                subsizes[n].push_back(dfsNum - prevNum)
        }
        
        minTouch = min(first, Num[k])
    }
    
    return minTouch;
}

Then, when you remove the articulation point n, you just print the sizes of the original components (except the component that contains node n), the data stored at subsizes[n] and the size of the original component that contained node n minus the sum of all the elements in subsizes[n] minus 1.

I think that should work, hopefully I'm not forgetting to consider something... maybe someone can help me around :)

EDIT: Yes, actually I was forgetting something. Since the graph is not a tree, one of children branches of node n can connect with the parent's branch, so we also need to keep track of 'first', the least numbered node that the branch touches. If first < Num[n], then we don't consider that branch as a subcomponent. I changed the code. I'm still quite not sure it'd work...