【每日一题Day311】LC1761一个图中连通三元组的最小度数 | 枚举

一个图中连通三元组的最小度数【LC1761】

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

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

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

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

来晚咯

• 思路

  • 使用数组记录每个节点的度数，即相连的边数；
  • 并记录每条边至哈希表中，每条边假定小指向大
  • 暴力枚举每个三元组，判断是否两两相连，如果是那么该三元组为连通三元组，其度数为[每个点度数之和-6]，判断能否更新结果
  • 枚举过程中，可以进行剪枝优化
    • 每个点的度数一定大于2
    • res为0时，可以直接返回结果

• 实现

  class Solution {public int minTrioDegree(int n, int[][] edges) {Set<Integer> 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;}
  }
  

  • 复杂度

    • 时间复杂度：$\mathcal{O}(n^3)$,n为点的个数

    • 空间复杂度：$\mathcal{O}(m)$，m为edges的长度