[LeetCode] Minimum Degree of a Connected Triplet in a Graph

Problem Description#

Given an undirected graph, an integer n representing the number of nodes in the graph, and an array edges representing the edges in the graph, where edges[i] = [ui, vi] represents an undirected edge between ui and vi.

A connected trio refers to a set of three nodes in which there is an edge between every pair of nodes.

The degree of a connected trio is the number of edges that satisfy this condition: one vertex is inside the trio, while the other vertex is not.

Please return the minimum value of the degrees among all connected trios. If there are no connected trios in the graph, return -1.

Operation Examples#

Example 1#

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is only one connected trio [1,2,3]. The edges that contribute to the degree are highlighted in the above graph.

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 3 connected trios:
1) [1,4,3], degree is 0.
2) [2,5,6], degree is 2.
3) [5,6,7], degree is 2.

Note#

2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi

There are no duplicate edges in the graph.

Code Example#

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:    
        degree=[0]*(n+1)
        g=defaultdict(set)
        for u,v in edges:
            degree[u]+=1
            degree[v]+=1
            if u>v:g[u].add(v)
            else:g[v].add(u)
        ans=inf
        for i in range(n+1):
            for j in g[i]:
                d=degree[i]+degree[j]-6
                if d+2>ans:continue
                t=min((degree[k] for k in g[i]&g[j]),default=inf)
                ans=min(ans,t+d)
        return ans if ans!=inf else -1