Last Updated: 3 Apr, 2021
Minimum Degree
Moderate
Asked in companies
You have an undirected graph with N nodes and M edges. The degree of the connected trio in the graph is the number of edges connected to the nodes of the trio where one node belongs to the node in the trio, while the other node doesn’t belong to the trio. Your task is to print the minimum degree of the connected trio.
Note:
A connected trio means a set of three nodes, where all three are interconnected.
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 nodes and number of edges.
Each of the next M lines contains two space-separated integers u and v, denoting node u and node v are connected by an edge.
Output Format:
For each test case, return an integer denoting the minimum degree of the connected trio.
Print the output for each test case in a separate line.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 3
2 <= N <= 100
0 <= M <= min(500, N*(N-1)/2)
0 <= u[i], v[i] <= N-1
where, ‘N’ and ‘M’ denoting the number of nodes and number of edges and u[i], v[i] are nodes to be connected by an edge.
Time Limit: 1 sec.
Approaches
- We know that the number of nodes connected to a node by an edge is equal to the degree of that node in a graph.
- We have to find the total number of edges connected to a connected trio of nodes in this problem.
- To find a connected trio we can just iterate over all trios of nodes and check if there is an edge between all pairs.
- After finding the trio of nodes what we can do to find the number of connected edges is to check the degree of nodes, here the number of edges where one node belongs to the node in the trio, while the other node doesn’t belong to the trio is equal to the degree of the node -2.
- Thus the answer will be the sum of degrees of all three nodes in the trio -6.
- In case there is no connected trio the answer will be 0.
Algorithm:
- Create an array ‘deg’ of size 'N', and initialize all indexes by 0, and a variable ‘ans’= INFINITY, where INFINITY is a large value that can never be our answer.
- Iterate over all the edges (i, j) and increment degrees of both nodes.
- Iterate over all the edges (i, j) again, and find another node ‘k’ that forms edge with both nodes, and update.
ans= min(ans, deg[ i ] + deg[ j ] + deg[ k ] - 6 )
- Return ‘ans’.