How do I solve the Minimum Degree of a Connected Trio in a Graph problem efficiently?

Use graph traversal techniques like BFS or DFS to reduce unnecessary checking of all node combinations. Prioritize nodes with higher degrees for better performance.

What is the key pattern in the Minimum Degree of a Connected Trio in a Graph problem?

The key pattern is using graph enumeration combined with degree counting to identify the trio with the minimum degree efficiently.

How do I calculate the degree of a connected trio?

The degree of a connected trio is calculated by counting the edges where one endpoint is part of the trio and the other is not. The degree is the sum of the individual degrees minus 6.

Can this problem be solved with a greedy approach?

A greedy approach might not always work, as it may not guarantee finding the optimal solution. Efficient graph enumeration with careful counting is the best approach.

What should I avoid when solving the Minimum Degree of a Connected Trio problem?

Avoid brute-force checking of all trios without optimization. Also, make sure to correctly count the edges and ensure that all nodes in the trio are connected.

#1761

Hard

auto_awesome图

LeetCode 题解工作台

一个图中连通三元组的最小度数

给你一个无向图，整数 n 表示图中节点的数目， edges 数组表示图中的边，其中 edges[i] = [u i , v i ] ，表示 u i 和 v i 之间有一条无向边。一个连通三元组指的是三个节点组成的集合且这三个点之间两两有边。连通三元组的度数是所有满足此条件的边的数目…

图枚举

题目描述

给你一个无向图，整数 n 表示图中节点的数目，edges 数组表示图中的边，其中 edges[i] = [u_i, v_i] ，表示 u_i 和 v_i之间有一条无向边。

一个 连通三元组 指的是三个节点组成的集合且这三个点之间两两有边。

连通三元组的度数 是所有满足此条件的边的数目：一个顶点在这个三元组内，而另一个顶点不在这个三元组内。

请你返回所有连通三元组中度数的 最小值 ，如果图中没有连通三元组，那么返回 -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 <= u_i, v_i <= n
u_i!= v_i
图中没有重复的边。

lightbulb

解题思路

方法一：暴力枚举

我们先将所有边存入邻接矩阵 $\textit{g}$ 中，再将每个节点的度数存入数组 $\textit{deg}$ 中。初始化答案 $\textit{ans}=+\infty$ 。

然后枚举所有的三元组 $(i, j, k)$ ，其中 $i \lt j \lt k$ ，如果 $\textit{g}[i][j] = \textit{g}[j][k] = \textit{g}[i][k] = 1$ ，则说明这三个节点构成了一个连通三元组，此时更新答案为 $\textit{ans} = \min(\textit{ans}, \textit{deg}[i] + \textit{deg}[j] + \textit{deg}[k] - 6)$ 。

枚举完所有的三元组后，如果答案仍然为 $+\infty$ ，说明图中不存在连通三元组，返回 $-1$ ，否则返回答案。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

def min(a: int, b: int) -> int:
    return a if a < b else b


class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        g = [[False] * n for _ in range(n)]
        deg = [0] * n
        for u, v in edges:
            u, v = u - 1, v - 1
            g[u][v] = g[v][u] = True
            deg[u] += 1
            deg[v] += 1
        ans = inf
        for i in range(n):
            for j in range(i + 1, n):
                if g[i][j]:
                    for k in range(j + 1, n):
                        if g[i][k] and g[j][k]:
                            ans = min(ans, deg[i] + deg[j] + deg[k] - 6)
        return -1 if ans == inf else ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of graph enumeration patterns and efficient counting techniques.
question_mark
Ability to apply traversal strategies for reducing unnecessary computations.
question_mark
Comfort with optimizing brute force solutions to scale to larger inputs.

warning

常见陷阱

外企场景

error
Incorrectly counting the degree of a trio by missing some edges between nodes.
error
Failing to properly check all connected trios, especially in sparse graphs.
error
Using brute force methods without optimization that could lead to excessive runtime for larger graphs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum degree of a connected trio.
arrow_right_alt
Handle directed graphs where the degree of a trio might change based on edge direction.
arrow_right_alt
Modify the problem to allow for weighted edges and find the minimum weighted degree of a connected trio.

help

常见问题

外企场景

继续练习

#2242 节点序列的最大得分 #1782 统计点对的数目 #1786 从第一个节点出发到最后一个节点的受限路径数