[力扣]一個圖中連通三元組的最小度數

题目簡介#

給你一個無向圖，整數 n 表示圖中節點的數目，edges 陣列表示圖中的邊，其中 edges [i] = [ui, vi] ，表示 ui 和 vi 之間有一條無向邊。

一個連通三元組指的是三個節點組成的集合且這三個點之間兩兩有邊。

連通三元組的度數是所有滿足此條件的邊的數目：一個頂點在這個三元組內，而另一個頂點不在這個三元組內。

請你返回所有連通三元組中度數的最小值，如果圖中沒有連通三元組，那麼返回 -1 。

操作示例#

示例 1#

輸入：n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
輸出：3
解釋：只有一個三元組 [1,2,3] 。構成度數的邊在上圖中已被加粗。

示例 2#

輸入：n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
輸出：0
解釋：有 3 個三元組：
1) [1,4,3]，度數為 0 。
2) [2,5,6]，度數為 2 。
3) [5,6,7]，度數為 2 。

提示#

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

圖中沒有重複的邊。

代碼示例#

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