Minimum Degree

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
eBayVFISLK Global Services

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
6 7 
0 1
0 3
1 2
1 3
2 3
2 4
1 5
4 0
Sample Output 1:
3
0
Explanation for Sample Input 1:
In test case 1:


There are two trios here in this graph [0, 1, 3] and [1, 2, 3].

In trio [0, 1, 3] : we have 3 edges where one node is connected to trio and other isn’t namely { (1-- 5) , (1 -- 2), (3 -- 2) }

In trio [ 1, 2, 3] : we have 4 edges where one node is connected to trio and other isn’t namely { (1-- 5) , (1 -- 0), (3 -- 0) , (2 -- 4) }

The minimum of the two is 3, hence the answer.

In test case 2:
There are no edges thus answer is 0.
Sample Input 2:
2
5 6
0 1
1 2
2 3
3 1
1 4
4 2
6 6
0 3
0 1
4 1
1 5
5 3
3 4
Sample Output 2:
3
0
Hint

Think to iterate over all trios of nodes and check if there is an edge between all pairs. Can you think of a solution now?

Approaches (1)
Brute Force

 

  • 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’.
Time Complexity

O(N ^ 3), where 'N' is the number of nodes in the graph

 

We are iterating over all the trio of nodes, which can reach up to N * (N-1) * (N-2) / 6 i.e.  O(N^3).

Space Complexity

O(N ^ 2), where ‘N’ is the number of nodes in the graph

 

We will be making an adjacency matrix in the problem. Thus space complexity is O(N^2).

Code Solution
(100% EXP penalty)
Minimum Degree
Full screen
Console