网站代码优化,北京建设协会网站首页,wordpress欢迎页面模板下载,门户站点是什么#xff08;leetcode1761一个图中连通三元组的最小度数#xff0c;暴力剪枝#xff09;-------------------Java实现
题目表述
给你一个无向图#xff0c;整数 n 表示图中节点的数目#xff0c;edges 数组表示图中的边#xff0c;其中 edges[i] [ui, vi] #xff0c;…leetcode1761一个图中连通三元组的最小度数暴力剪枝-------------------Java实现
题目表述
给你一个无向图整数 n 表示图中节点的数目edges 数组表示图中的边其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一条无向边。
一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。
连通三元组的度数 是所有满足此条件的边的数目一个顶点在这个三元组内而另一个顶点不在这个三元组内。
请你返回所有连通三元组中度数的 最小值 如果图中没有连通三元组那么返回 -1 。
样例 输入n 6, edges [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]] 输出3 解释只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。 输入n 7, edges [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]] 输出0 解释有 3 个三元组
[1,4,3]度数为 0 。[2,5,6]度数为 2 。[5,6,7]度数为 2 。
条件
2 n 400 edges[i].length 2 1 edges.length n * (n-1) / 2 1 ui, vi n ui ! vi 图中没有重复的边。
思路
暴力剪枝
注意点
ac代码
Java:
class Solution {public int minTrioDegree(int n, int[][] edges) {int[][] edge new int[n1][n1];int[] sum new int[n1];int min 3000;for (int[] line:edges) {if (line[0] line[1])edge[line[1]][line[0]];elseedge[line[0]][line[1]];sum[line[0]];sum[line[1]];}for (int i 1;in;i) {int now_sum0;for (int j i1; j n; j) {if (edge[i][j] 0)continue;now_sum;for (int z j1; z n; z) {if (edge[i][z]!0edge[j][z]!0){int now_edge_sum sum[i]sum[j]sum[z]-6;min Math.min(now_edge_sum,min);}}if (now_sumsum[i])break;}}return (min3000)?-1:min;}
}来源力扣LeetCode 链接https://leetcode-cn.com/problems/squares-of-a-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
