Page Contents

**Shopping Patterns Minimum Degree of a Connected Trio in a Graph**

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [u_{i}, v_{i}] indicates that there is an undirected edge between u_{i} and v_{i}.

A **connected trio** is a set of **three** nodes where there is an edge between **every** pair of them.

The **degree of a connected trio** is the number of edges where one endpoint is in the trio, and the other is not.

Return *the **minimum** degree of a connected trio in the graph, or* -1 *if the graph has no connected trios.*

**Example 1:**

**Input:** n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]

**Output:** 3

**Explanation:** There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

**Example 2:**

**Input:** n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]

**Output:** 0

**Explanation:** There are exactly three trios:

- [1,4,3] with degree 0.
- [2,5,6] with degree 2.
- [5,6,7] with degree 2.

**Constraints:**

- 2 <= n <= 400
- edges[i].length == 2
- 1 <= edges.length <= n * (n-1) / 2
- 1 <= u
_{i}, v_{i}<= n - u
_{i }!= v_{i} - There are no repeated edges.

**SOLUTION**

** Program**:

**Shopping Patterns**Solution in C++

```
class Solution {
public:
bool visited[401][401];
int minTrioDegree(int n, vector<vector<int>>& edges) {
vector<unordered_set<int>>adj(n+1);
memset(visited,false,sizeof(visited));
int degree[n+1];
for(int i=0;i<n+1;i++)
degree[i]=0;
for(int i=0;i<edges.size();i++){
int start = edges[i][0];
int end = edges[i][1];
visited[start][end]=true;
visited[end][start]=true;
degree[start]++;
degree[end]++;
}
int result = INT_MAX;
for(int i=1;i<=n-2;i++){
for(int j=i+1;j<=n-1;j++){
for(int k=j+1;k<=n;k++){
if(connected(i,j,k)){
int count = 0;
count+=degree[i]-2;
count+=degree[j]-2;
count+=degree[k]-2;
result=min(result,count);
}
}
}
}
return result==INT_MAX ? -1: result;
}
bool connected(int i,int j,int k){
if(!visited[i][j] || !visited[i][k])
return false;
if(!visited[j][i] || !visited[j][k])
return false;
if(!visited[k][i] || !visited[k][j])
return false;
return true;
}
};
```

** Program**:

**Shopping Patterns**Solution in Python

```
class Solution:
def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
g = defaultdict(set)
for a, b in edges:
g[a].add(b)
g[b].add(a)
d = {n:len(g[n]) for n in g}
res = inf
for n in g:
for m in g[n]:
for o in g[n] & g[m]:
res = min(res, d[n]+d[m]+d[o]-6)
g[o].discard(n)
g[m].discard(n)
return res if res < inf else -1
```

** Program**:

**Shopping Patterns**Solution in Java

**Explanation:**

- The HashMap degrees keeps track of the degree for each vertex.
- boolean[][] isEdge keeps track of whether (i, j) is an edge.
- Then we just iterate through all edges (i, j), and for each edge, iterate through all nodes k, if (i, k) and (j, k) are also edges, then this is a trio. We just use the degrees we stored in the hashmap to calculate the total degrees.
- The complexity is O(E * V), where E is the number of edges, and V is the number of vertices (which is N). In worst case scenario, there would be ~N^2 edges, so the time complexity is O(N^3).

```
class Solution {
public int minTrioDegree(int n, int[][] edges) {
int min = Integer.MAX_VALUE;
Map<Integer, Integer> degrees = new HashMap<>(); // vertex, degree
boolean[][] isEdge = new boolean[n + 1][n + 1];
for (int[] edge : edges) {
degrees.put(edge[0], degrees.getOrDefault(edge[0], 0) + 1);
degrees.put(edge[1], degrees.getOrDefault(edge[1], 0) + 1);
isEdge[edge[0]][edge[1]] = true;
isEdge[edge[1]][edge[0]] = true;
}
for (int[] edge : edges) {
for (int i = 1; i <= n; i++) {
if (isEdge[i][edge[0]] && isEdge[i][edge[1]]) {
// subtract 6 because we do not count inner edges of a trio
int degree = degrees.get(i) + degrees.get(edge[0]) + degrees.get(edge[1]) - 6;
min = Math.min(min, degree);
}
}
}
if (min == Integer.MAX_VALUE)
return -1;
return min;
}
}
```

*Related: Amazon OA Online Assessment 2021 Questions and Answers*