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

题意

  • 寻找所有的连通三元组
  • 返回连通三元组的最小度

code – 1 BFS

一开始的想法是使用 bfs，只要层次遍历三层即可。但是用递归写法会超时，后改成递推写法，注意：

  • 要存储第二层的点。我直接将第二层的点和第三层的点一起 push 进了队列中；
  • 为了减少重复的三元组，只在升序三元组中寻找连通三元组；
class Solution {public:int maxn = 1e9+10;int ans = maxn;void bfs(int u, vector<vector<int>> g, vector<int> in){// 遍历含有顶点 u 的连通三元组int cnt = 1, curCnt = 0, preCnt = 1;queue<int> q;q.push(u);vector<int> pre(g.size(), -1);while(cnt <= 3){if(cnt == 3) // 三元组{while(!q.empty()){int pre = q.front();q.pop();int cur = q.front();q.pop();if(cur > pre && g[cur][u] == 1) // 三元组是否连通{int tmp = in[u] + in[pre] + in[cur] - 6;ans = min(ans, tmp);}}}if(q.empty()) break;curCnt = 0;while(preCnt){int cur = q.front();q.pop();preCnt--;for(int i = cur + 1; i < g[cur].size(); i++){if(g[cur][i] == 1)// 邻接点{if(cnt == 2) q.push(cur); // 保存第2个点q.push(i);curCnt++;}}}preCnt = curCnt;cnt++;}}int minTrioDegree(int n, vector<vector<int>>& edges) {vector<vector<int> > g(n + 1, vector<int>(n + 1, maxn));vector<int> in(n + 1, 0);for(int i = 0; i < edges.size(); i++){g[edges[i][0]][edges[i][1]] = 1;g[edges[i][1]][edges[i][0]] = 1;in[edges[i][0]]++;in[edges[i][1]]++;}for(int i = 1; i <= n; i++){bfs(i, g, in);cout<<endl;}return ans == maxn ? -1 : ans;}};

code – 2 暴力解法

暴力遍历所有的三元组，同时为了减少重复的三元组，只检查升序三元组。

class Solution {public:int maxn = 1e9+10;int minTrioDegree(int n, vector<vector<int>>& edges) {vector<vector<int> > g(n + 1, vector<int>(n + 1, maxn));vector<int> in(n + 1, 0);int ans = maxn;for(int i = 0; i < edges.size(); i++){g[edges[i][0]][edges[i][1]] = 1;g[edges[i][1]][edges[i][0]] = 1;in[edges[i][0]]++;in[edges[i][1]]++;}for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){for(int k = j + 1; k <= n; k++){if(g[i][j] == 1 && g[j][k] == 1 && g[k][i] == 1){int tmp = in[i] + in[j] + in[k] - 6;ans = min(tmp, ans);}}}}return ans == maxn ? -1 : ans;}};

复杂度

时间复杂度：O(N3)
空间复杂度：O(N2)