如何选择一家好的网站建设公司,网站建设网络推广最低价格,中国空间站视频,公司实力 网站一个图中连通三元组的最小度数【LC1761】 给你一个无向图#xff0c;整数 n 表示图中节点的数目#xff0c;edges 数组表示图中的边#xff0c;其中 edges[i] [ui, vi] #xff0c;表示 ui 和 vi 之间有一条无向边。 一个 连通三元组 指的是 三个 节点组成的集合且这三个点…一个图中连通三元组的最小度数【LC1761】 给你一个无向图整数 n 表示图中节点的数目edges 数组表示图中的边其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一条无向边。 一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。 连通三元组的度数 是所有满足此条件的边的数目一个顶点在这个三元组内而另一个顶点不在这个三元组内。 请你返回所有连通三元组中度数的 最小值 如果图中没有连通三元组那么返回 -1 。 来晚咯 思路 使用数组记录每个节点的度数即相连的边数并记录每条边至哈希表中每条边假定小指向大暴力枚举每个三元组判断是否两两相连如果是那么该三元组为连通三元组其度数为[每个点度数之和-6]判断能否更新结果枚举过程中可以进行剪枝优化 每个点的度数一定大于2res为0时可以直接返回结果 实现 class Solution {public int minTrioDegree(int n, int[][] edges) {SetInteger 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;}
}复杂度 时间复杂度 O ( n 3 ) \mathcal{O}(n^3) O(n3),n为点的个数 空间复杂度 O ( m ) \mathcal{O}(m) O(m)m为edges的长度
