How good would cutting the bridges be?

The problem asks us to first destroy all the bridges of the kingdom and then find the largest component of the resulting graph. For this, we start by identifying the bridges of the graph. Have a look at the solution of the problem cut the bridges and conquer to know how we find the bridge edges of a graph. (Explaining the code for finding bridges would make the solution really lengthy @Agnishom Chattopadhyay have explained very nicely in the above linked solution).

To be precise, the bridge edges comes out to be : {169,20} , {5,225} , {15,247} , {120,154} , {245,212} , {1,245} (The pairs here is not ordered i.e {a,b} and {b,a} both needs to be removed for all {a,b} )

Having found the bridge edges, remove the bridge edges from the adjacency list.

Now, we have a graph and the problem asks to find the size of largest component in it. We can find the size of each component by any graph exploration algorithm depth first search or breadth first search . The following explains to use depth first search.

So, how exactly do we do this? Its simple. Whenever we start exploring a node, we end up exploring all the nodes accessible from that node. In other words, we explore all the nodes in the component of our starting node. Just keep a counter "presentCount" and increase it when you encounter a new node. Set the value of "presentCount" to 0 at the start of exploration of each new component. Also keep a variable "ans" which is here to keep track of the largest component size.

This way, we visit all components and pick up the largest component size as our answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//adjacencyVector already initialized and processed to remove bridges. 
int ans=0,presentCounter=0;
std::vector<bool> visitedNodes;
int dfs(int node)
{
    visitedNodes[node]=1;++presentCounter;
    for(auto it:AdjacencyVector[node])
    {
        if(!visitedNodes[it])
        {
            dfs(it);
        }
    }
    return 0;
}
int findLargestComponent()
{
    visitedNodes.resize(n,0);
    for(int node=0;node<n;++node)
    {
        if(visitedNodes[node]==0)
        {
            dfs(node);
            ans=max(ans,presentCounter);
            presentCounter=0;
        }
    }
    cout<<ans;
    return ans;
}