【C++图论】1761. 一个图中连通三元组的最小度数|2005

本文涉及知识点

C++图论

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

给你一个无向图，整数 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,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
图中没有重复的边。

图论

枚举三个节点(i,j,k) i <j <k ，时间复杂度：O(nnn/6)，如果细节没处理好，可能会超时。
连接矩阵mat 记录i,j是否连通。
deg[i]记录和i连接的边数。
（i,j,k)的度数就是deg(i)+deg(j)+deg(k)-6

代码

核心代码

class Solution {public:int minTrioDegree(int n, vector<vector<int>>& edges) {int ans = INT_MAX;vector<vector<bool>> mat(n, vector<bool>(n));vector<int> deg(n);for (const auto& v : edges) {mat[v[0] - 1][v[1] - 1] = true;mat[v[1] - 1][v[0] - 1] = true;deg[v[0] - 1]++;deg[v[1] - 1]++;}for(int i = 0 ; i < n ; i++ )for(int j = i+1; j < n; j++ )for (int k = j + 1; k < n; k++) {if (!mat[i][j] || !mat[i][k] || !mat[j][k])continue;ans = min(ans, deg[i] + deg[j] + deg[k] -6);}return INT_MAX == ans ? -1 : ans;}};

单元测试

int n;vector<vector<int>> edges;TEST_METHOD(TestMethod11){n = 6, edges = { {1,2},{1,3},{3,2},{4,1},{5,2},{3,6} };auto res = Solution().minTrioDegree(n, edges);AssertEx(3, res);}TEST_METHOD(TestMethod12){n = 7, edges = { {1,3},{4,1},{4,3},{2,5},{5,6},{6,7},{7,5},{2,6} };auto res = Solution().minTrioDegree(n, edges);AssertEx(0, res);}TEST_METHOD(TestMethod13){n = 3, edges = { {1,2},{2,3},{1,3} };auto res = Solution().minTrioDegree(n, edges);AssertEx(0, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功