タイトルの概要#
与えられた無向グラフについて、整数 n はグラフのノードの数を表し、edges 配列はグラフの辺を表します。ここで、edges [i] = [ui, vi] は、ui と vi の間に無向辺があることを示します。
連結三つ組は、3 つのノードからなる集合であり、これらの 3 つの点の間には 2 つの辺があります。
連結三つ組の次数は、この条件を満たすすべての辺の数です：1 つの頂点がこの三つ組に含まれ、もう 1 つの頂点がこの三つ組に含まれていない。
連結三つ組の次数の最小値を返し、グラフに連結三つ組がない場合は - 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