本文共 2145 字，大约阅读时间需要 7 分钟。

题目

给你一个无向图，整数 n 表示图中节点的数目，edges 数组表示图中的边，其中 edges[i] = [ui, vi] ，表示 ui 和 vi 之间有一条无向边。

一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。

连通三元组的度数 是所有满足此条件的边的数目：一个顶点在这个三元组内，而另一个顶点不在这个三元组内。

请你返回所有连通三元组中度数的 最小值 ，如果图中没有连通三元组，那么返回 -1 。

示例一

提示：

• 2 <= n <= 400
• edges[i].length == 2
• 1 <= edges.length <= n * (n-1) / 2
• 1 <= ui, vi <= n
• ui != vi
  图中没有重复的边。

思路一

因为n<400,n^3在暴搜的范围内是可以接受的，因此我们可以采用暴搜的方法。

• 首先算出每个节点的度数。
• 其次判断三个节点是否成环，成环之后，判断其度的最小值。

代码

const int maxn = 405;class Solution {
   public:    int minTrioDegree(int n, vector
   
    
     >& edges) {
           int degree[maxn] = {
   0}, edge[maxn][maxn] = {
   0};        for(auto d : edges){
               edge[d[0]][d[1]] = edge[d[1]][d[0]] = 1;            degree[d[0]]++, degree[d[1]]++;        }        int ans = 0x3f3f3f3f;        for(int i = 1;i <= n;i++){
               for(int j = i + 1;j <= n;j++){
                   if(edge[i][j]){
                       for(int k = j + 1;k <= n;k++){
                           if(edge[j][k] && edge[k][i]){
                               ans = min(ans, degree[i] + degree[j] + degree[k] - 6 );                        }                    }                }            }        }        if(ans == 0x3f3f3f3f) return -1;        return ans;    }};
    
   

思路二

算法的思路还是不变化的，但是我们可以采用这个stl库来优化访问。

代码

const int maxn = 405;class Solution {
   public:    int minTrioDegree(int n, vector
   
    
     >& edges) {
           bitset
     
       b[maxn];        for(auto d : edges){
               b[d[0]].set(d[1]);            b[d[1]].set(d[0]);        }        int degree[maxn] = {
   0}, ans = 0x3f3f3f3f;        for(int i = 1;i <= n;i++) degree[i] = b[i].count();        for(int i = 1;i < n - 1;i++){
               for(int j = b[i]._Find_next(i); j < n;j = b[i]._Find_next(j)){
                   auto k = b[i] & b[j];                for(int p = k._Find_next(j); p <= n; p = k._Find_next(p)){
                       ans = min(ans, degree[i] + degree[j] + degree[p] - 6);                }            }        }        if(ans == 0x3f3f3f3f) return -1;        else return ans;    }};
     
    
   

转载地址：https://blog.csdn.net/free1993/article/details/114282487 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！