【力扣每日一题】2023.8.31 一个图中连通三元组的最小度数

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目给我们一个无向图，要我们找出三个节点，这三个节点他们两两相连，这三个节点除了连接到对方的其他线被称为连通三元组的度数，问我们图中最小的三元组度数是多少。

我的第一个想法就是使用map来构建图，然后遍历每个节点，再遍历每个节点的相邻节点，再遍历每个节点的相邻节点的相邻节点，如果节点的相邻节点的相邻节点是该节点，那么我们就找到了连通三元组，他们总体的度数-6就是连通三元组的度数。因为三元组中每个节点为了连通另外两个节点，都需要花费两个度，而剩余的度就是连接其他非本三元组的节点了，所以连通三元组的度数就是三个节点的总度数-2*3。

不过这么做就超时了，因为同一个三元组我们会重复遍历三次，每个节点我们都会遍历寻找包括它的连通三元组。虽然这种方式超时了，但也不失为一种方法，代码在下面，可以参考。

那么直接构建图不行，我们可以构建图的邻接矩阵。

我们另外再拿一个数组来存放每个节点的度数。

邻接矩阵用来判断三个点是否是相互连通的，度数数组用来计算连通三元组的度数。

代码：

class Solution {
public:int minTrioDegree(int n, vector<vector<int>>& edges) {//超时unordered_map<int,unordered_set<int>>m;for(auto edge:edges){   //构建图if(m.find(edge[0])==m.end()) m[edge[0]]=unordered_set<int>();if(m.find(edge[1])==m.end()) m[edge[1]]=unordered_set<int>();m[edge[0]].insert(edge[1]);m[edge[1]].insert(edge[0]);}int res=INT_MAX;for(auto& i:m){     //取出每个节点for(auto& j: i.second){     //取出相连的节点集for(auto& k: m[j]){         //取出相连的节点的相连结果集if(m[k].count(i.first)){    //若是等于第一个节点,那么表示这仨节点相互连通res=min(res,static_cast<int>(i.second.size()+m[j].size()+m[k].size()-6));}}}}return res==INT_MAX?-1:res;//构建邻接矩阵 int res=INT_MAX;vector<vector<int>>pic(n+1,vector<int>(n+1,0)); //连通矩阵vector<int>du(n+1,0);   //每个点的度for(auto& edge: edges){     //构建邻接矩阵以及获取每个节点的度pic[edge[0]][edge[1]]=1;pic[edge[1]][edge[0]]=1;du[edge[0]]++;du[edge[1]]++;} for(int i=1;i<=n;i++){  for(int j=i+1;j<=n;j++){for(int k=j+1;k<=n;k++){//遍历每个节点,找到相互连通的三个节点,度数之和-6就是连通三元组的读度数if(pic[i][j] && pic[j][k] && pic[i][k]) res=min(res,du[i]+du[j]+du[k]-6);}}}return res==INT_MAX?-1:res;}
};