complete all connected components, then unite all capitalless components to largest component which has government home

There are K nodes corresponding to governments and none of them are initially connected by any path and you should never connect any of them by some path. So basically there are some connected components initially. You find each of those connected components by dfs. You will not connect any two nodes of different connected components because of the condition in the first line. For each connected component maximum number of edges that you can put is n*(n-1)/2 where n is the number of nodes in that connected component. Some edges were already in the connected component so you can just subtract their amount to get the number of "new" edges that you can put.

Now some connected components might not contain any government node. You can actually merge these connected components into one large connected component and this way you may put more edges into the graph. And also you can merge all of them with a connected component that already has a government node. This way you can form one large connected component and you want that to be largest (greedy thinking). So pick the largest connected component with a government node and merge all of the "connected components without government node" with this component to make one large component. And now you can calculate total number of edges you can insert into graph.