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

标签: 图

难度: 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
解释：有 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
  • 图中没有重复的边。

Submission

运行时间: 88 ms

内存: 30.6 MB

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        # 相邻节点按度数排序+元组BFS加速查找
        maps = collections.defaultdict(list)
        for s, e in edges:
            maps[s].append(e)
            maps[e].append(s)
        res = float("inf")
        for i in range(1, n + 1):
            if len(maps[i]) < 2:
                # 当前节点的相邻节点数小于2
                continue
            # 对相邻节点的度数进行排序, 这样可以保证后面先遍历的元组组合的度数更小
            arr = sorted(maps[i], key=lambda x: len(maps[x]))
            # 按层BFS, 从最小元组开始遍历
            q = [(0, 1)]
            v = set(q)
            found = False
            for l, r in q:
                if found:
                    # 找到一个有效三元组了, 其度数组合一定是包含节点i的三元组中最小的, 不再继续遍历其他的
                    break
                j, k = arr[l], arr[r]
                if j in maps[k]:
                    # 找到一个有效的三元组, 将found标记置为True, 并更新res
                    found = True
                    res = min(res, len(maps[i]) + len(maps[j]) + len(maps[k]) - 6)
                else:
                    # 否则两个方向继续找下一个元组组合
                    for nl, nr in ((l + 1, r), (l, r + 1)):
                        if 0 <= nl < len(arr) and 0 <= nr < len(arr) and nl != nr and (nl, nr) not in v:
                            # 当前元组尚未遍历, 将其放到队列末尾等待遍历
                            v.add((nl, nr))
                            q.append((nl, nr))
        return -1 if res == float("inf") else res

Explain

此题解采用的是一种基于邻接表的方法来查找图中所有的连通三元组，并计算它们的度数。首先，使用一个哈希表 `maps` 来存储每个节点的邻接节点。对于每个节点 `i`，如果它的邻接节点少于两个，则无法形成三元组，跳过这样的节点。对于其他节点，首先对它们的邻接节点按照邻接节点数进行排序，以便优先处理可能形成连通三元组的节点组合。使用一种类似于广度优先搜索的方法来穷举所有可能的三元组组合，一旦找到一个有效的三元组，即计算其度数并更新最小度数。如果在遍历过程中发现存在度数更小的三元组，则更新结果 `res`。最终，如果没有找到任何连通三元组，返回 -1，否则返回最小的度数。

时间复杂度: O(n^3)

空间复杂度: O(E + n^2)

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        # 创建邻接表
        maps = collections.defaultdict(list)
        for s, e in edges:
            maps[s].append(e)
            maps[e].append(s)
        res = float('inf')
        # 遍历每个节点
        for i in range(1, n + 1):
            if len(maps[i]) < 2:
                continue # 跳过度数小于2的节点
            # 对邻接节点按度数排序
            arr = sorted(maps[i], key=lambda x: len(maps[x]))
            # 使用BFS寻找三元组
            q = [(0, 1)]
            v = set(q)
            found = False
            for l, r in q:
                if found:
                    break # 找到最小三元组后停止
                j, k = arr[l], arr[r]
                if j in maps[k]:
                    found = True
                    res = min(res, len(maps[i]) + len(maps[j]) + len(maps[k]) - 6)
                else:
                    # 将新的节点对加入队列
                    for nl, nr in ((l + 1, r), (l, r + 1)):
                        if 0 <= nl < len(arr) and 0 <= nr < len(arr) and nl != nr and (nl, nr) not in v:
                            v.add((nl, nr))
                            q.append((nl, nr))
        return -1 if res == float('inf') else res

Explore

在算法中，确保三个节点i, j, k形成连通三元组的依据是对每个节点i遍历其邻接节点列表arr，检查任意两个节点j和k（从arr中选择）是否存在于彼此的邻接列表中。具体地，对于每对j和k，我们检查j是否在节点k的邻接列表maps[k]中。只有当i, j和k两两直接相连，即i与j相连，i与k相连，且j与k相连时，它们才被视为一个有效的连通三元组。

虽然题解中提到使用类似BFS的方法，但实际的实现更类似于广度优先搜索的变体。这里使用队列q来存储待检查的节点对索引(l, r)，这些索引对应于节点i的邻接节点arr中的元素。队列的初始状态是(0, 1)，表示检查arr中的第一个和第二个元素。访问集合v用于记录已经访问过的节点对索引，以避免重复处理相同的节点对。对于队列中的每个元素(l, r)，检查通过这些索引在arr中找到的节点j和k是否形成一个三元组。若不满足条件，将新的节点对索引加入队列，继续检查。

在计算三元组的度数时，我们首先计算三个节点i, j, k的度数之和。然而，因为每个边被计算了两次（每个节点对其邻接节点的连接），所以i, j, k之间的三条内部边也被重复计算了。这导致总度数被多计算了6（每条边计算两次，共3条边）。因此，我们从总和中减去6，以得到实际的外部连通度数，即除去三元组内部的连接之外，各节点还与外部有多少连接。

一个节点要形成三元组，至少需要与两个其他节点连通。如果一个节点的邻接节点少于两个，则意味着它不可能与两个其他节点形成完全连接的三元组。因此，对于那些邻接节点少于两个的节点，我们可以直接跳过，因为它们无法构成所需的连通三元组。这是一个基于图的结构性质的有效优化，避免了不必要的计算。