问题描述
给你一个无向图，整数 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 <= 400edges[i].length == 21 <= edges.length <= n * (n-1) / 21 <= ui, vi <= nui != vi- 图中没有重复的边。
解题思路
暴力 \(\mathcal{O}(n^3)\) 就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
conn = [[False for _ in range(n)] for _ in range(n)]
deg = [0] * n
for u, v in edges:
u, v = u - 1, v - 1
conn[u][v] = conn[v][u] = True
deg[u] += 1
deg[v] += 1
INF = 10 ** 9
ans = INF
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if conn[i][j] and conn[i][k] and conn[j][k]:
ans = min(ans, deg[i] + deg[j] + deg[k] - 6)
return -1 if ans == INF else ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | const int N = 405;
const int INF = 1000000000;
class Solution {
public:
int minTrioDegree(int n, vector<vector<int>>& edges) {
int conn[N][N] = {0};
int deg[N] = {0};
for (auto &e : edges) {
int u = e[0] - 1, v = e[1] - 1;
conn[u][v] = conn[v][u] = 1;
++deg[u], ++deg[v];
}
int ans = INF;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (conn[i][j] && conn[i][k] && conn[j][k]) {
ans = min(ans, deg[i] + deg[j] + deg[k] - 6);
}
}
}
}
return ans == INF ? -1 : ans;
}
};
|