一个图中连通三元组的最小度数【LC1761】
给你一个无向图，整数
n表示图中节点的数目，edges数组表示图中的边，其中edges[i] = [ui, vi]，表示ui和vi之间有一条无向边。一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。
连通三元组的度数 是所有满足此条件的边的数目：一个顶点在这个三元组内，而另一个顶点不在这个三元组内。
请你返回所有连通三元组中度数的 最小值 ，如果图中没有连通三元组，那么返回
-1。
来晚咯
- 思路
- 使用数组记录每个节点的度数，即相连的边数；
- 并记录每条边至哈希表中，每条边假定小指向大
- 暴力枚举每个三元组，判断是否两两相连，如果是那么该三元组为连通三元组，其度数为[每个点度数之和-6]，判断能否更新结果
- 枚举过程中，可以进行剪枝优化
- 每个点的度数一定大于2
- res为0时，可以直接返回结果
- 实现
class Solution { public int minTrioDegree(int n, int[][] edges) { Set<Integer> set = new HashSet<>(); int[] deg = new int[n]; for (int[] edge : edges){ int u = edge[0] - 1, v = edge[1] - 1; if (u > v){ int tmp = u; u = v; v = tmp; } set.add(u * n + v); deg[u]++; deg[v]++; } int res = Integer.MAX_VALUE; for (int i = 0; i < n; i++){ if (deg[i] < 2) continue; for (int j = i + 1; j < n; j++){ if (!set.contains(i * n + j) || deg[j] < 2) continue; for (int k = j + 1; k < n; k++){ if (deg[k] < 2) continue; if (set.contains(i * n + k) && set.contains(j * n + k)){ res = Math.min(res, deg[i] + deg[j] + deg[k] - 6); if (res == 0) return 0; } } } } return res == Integer.MAX_VALUE ? -1 : res; } }
