Hard

题目描述

给你一个无向图。给你一个整数 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
解释：有三个三元组：
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
  • 没有重复的边

解题思路

解题思路

这道题需要找到图中所有的连通三元组（三个节点两两相连），并计算每个三元组的度数，返回最小度数。

核心观察： 对于三元组 (u, v, w)，其度数等于 degree(u) + degree(v) + degree(w) - 6。这里减去 6 是因为三个节点之间的三条边（u-v, u-w, v-w）在计算各节点度数时被重复计算了两次。

算法步骤：

  1. 建图和计算度数：使用邻接矩阵存储图的连接关系，同时记录每个节点的度数。

  2. 枚举三元组：

    • 外层循环遍历节点 u
    • 中层循环遍历 u 的所有邻居节点 v
    • 内层循环遍历 u 的所有邻居节点 w（w > v 避免重复）
    • 检查 v 和 w 是否相连，若相连则形成三元组

  3. 计算度数：使用公式 degree(u) + degree(v) + degree(w) - 6 计算三元组度数。

  4. 优化：为了避免重复计算，在枚举时确保 v < w，这样每个三元组只会被计算一次。

时间复杂度：O(n³) - 三层循环枚举所有可能的三元组 空间复杂度：O(n²) - 邻接矩阵存储图

代码实现

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<vector<bool>> graph(n + 1, vector<bool>(n + 1, false));
        vector<int> degree(n + 1, 0);
        
        // 建图并计算度数
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u][v] = graph[v][u] = true;
            degree[u]++;
            degree[v]++;
        }
        
        int minDegree = INT_MAX;
        
        // 枚举所有可能的三元组
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                if (v != u && graph[u][v]) {
                    for (int w = v + 1; w <= n; w++) {
                        if (w != u && graph[u][w] && graph[v][w]) {
                            // 找到三元组 (u, v, w)
                            int trioDegree = degree[u] + degree[v] + degree[w] - 6;
                            minDegree = min(minDegree, trioDegree);
                        }
                    }
                }
            }
        }
        
        return minDegree == INT_MAX ? -1 : minDegree;
    }
};

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        graph = [[False] * (n + 1) for _ in range(n + 1)]
        degree = [0] * (n + 1)
        
        # 建图并计算度数
        for u, v in edges:
            graph[u][v] = graph[v][u] = True
            degree[u] += 1
            degree[v] += 1
        
        min_degree = float('inf')
        
        # 枚举所有可能的三元组
        for u in range(1, n + 1):
            for v in range(1, n + 1):
                if v != u and graph[u][v]:
                    for w in range(v + 1, n + 1):
                        if w != u and graph[u][w] and graph[v][w]:
                            # 找到三元组 (u, v, w)
                            trio_degree = degree[u] + degree[v] + degree[w] - 6
                            min_degree = min(min_degree, trio_degree)
        
        return -1 if min_degree == float('inf') else min_degree

public class Solution {
    public int MinTrioDegree(int n, int[][] edges) {
        bool[,] graph = new bool[n + 1, n + 1];
        int[] degree = new int[n + 1];
        
        // 建图并计算度数
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1];
            graph[u, v] = graph[v, u] = true;
            degree[u]++;
            degree[v]++;
        }
        
        int minDegree = int.MaxValue;
        
        // 枚举所有可能的三元组
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                if (v != u && graph[u, v]) {
                    for (int w = v + 1; w <= n; w++) {
                        if (w != u && graph[u, w] && graph[v, w]) {
                            // 找到三元组 (u, v, w)
                            int trioDegree = degree[u] + degree[v] + degree[w] - 6;
                            minDegree = Math.Min(minDegree, trioDegree);
                        }
                    }
                }
            }
        }
        
        return minDegree == int.MaxValue ? -1 : minDegree;
    }
}

var minTrioDegree = function(n, edges) {
    const adj = Array(n + 1).fill().map(() => new Set());
    const degree = Array(n + 1).fill(0);
    
    for (const [u, v] of edges) {
        adj[u].add(v);
        adj[v].add(u);
        degree[u]++;
        degree[v]++;
    }
    
    let minDegree = Infinity;
    
    for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
            if (adj[i].has(j)) {
                for (let k = j + 1; k <= n; k++) {
                    if (adj[i].has(k) && adj[j].has(k)) {
                        const trioDegree = degree[i] + degree[j] + degree[k] - 6;
                        minDegree = Math.min(minDegree, trioDegree);
                    }
                }
            }
        }
    }
    
    return minDegree === Infinity ? -1 : minDegree;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n³)
空间复杂度O(n²)

说明：

  • 时间复杂度：三层嵌套循环枚举所有可能的三元组，每次检查是否形成连通三元组的时间为 O(1)
  • 空间复杂度：使用邻接矩阵存储图的连接关系，需要 O(n²) 的空间

相关题目