Last Updated: 1 Apr, 2021
Max Town Order
Easy
Asked in company
Suppose there is a city of N towns and M bidirectional roads. The town order of two different towns is defined as the total number of directly connected roads to either town. If a road is directly connected to both towns, it is only counted once. The maximal town order of the city is the maximum town order of all pairs of different towns. Your task in this problem is to print the maximal town order of the city.
Input Format :
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains ‘N’ and ‘M’ denoting the number of towns and number of roads.
Each of the next M lines contains two space-separated integers u and v, denoting town u and town v are connected by a road.
Output Format :
For each test print an integer denoting the maximal town order of the city.
Note :
Don't print anything it has already been taken care of. Just implement the given function
Constraints :
1 <= T <= 3
2 <= N <= 100
0 <= M <= N*(N-1)/2
0 <= u[i], v[i] <= N-1
Where u[i], v[i] are towns to be connected by a road.
Time Limit: 1 second
Approaches
We know that in a graph, the number of nodes connected to a node by an edge is equal to the degree of that node.
In this problem, we have to find the total number of directly connected roads to either of the two towns. Since we want to find the number of roads connected to two towns we can just add the degrees of the two towns to get the answer.
Except that this will give an incorrect answer when the two towns are connected. In this case, we just need to subtract 1 from the sum of degrees. This is done because if two towns are connected by a road then in degrees both the towns we will have a common road ( which is connecting them), so we will subtract 1.
Therefore.
Answer = max { deg[ i ] + deg[ j ] - isConnected( i, j ) }
deg[ i ] = degrees of town ‘i’, i.e. number of towns connected by road to town ‘i’.
The function isConnected() returns 1 is both towns are connected else returns 0.
Algorithm:
- Create an array ‘deg’ of size N, and initialize all indexes by 0, and a variable ‘ans’= 0.
- Iterate over all the roads (u, v) and increment degrees of both towns.
- Iterate over all the roads again, and update
ans= max(ans, deg[ u ] + deg[ v ] - isConnected(u, v) )
- The function isConnected implemented by initially mapping all roads then checking if the (u, v) exists in the map or just implement an adjacency matrix for it.
- Return ‘ans’.