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

链接：1761.一个图中连通三元组的最小度数
难度：Hard
标签：图
简介：请你返回所有连通三元组中度数的 最小值 ，如果图中没有连通三元组，那么返回 -1 。

题解 1 - cpp

• 编辑时间：2023-08-31
• 执行用时：1896ms
• 内存消耗：53.2MB
• 编程语言：cpp
• 解法介绍：枚举。

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> nodes(n);
        for (auto &edge : edges) {
            nodes[edge[0] - 1].insert(edge[1] - 1);
            nodes[edge[1] - 1].insert(edge[0] - 1);
        }
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!nodes[i].count(j)) continue;
                for (int k = j + 1; k < n; k++) {
                    if (!nodes[i].count(k) || !nodes[j].count(k)) continue;
                    res = min(res, (int)nodes[i].size() + (int)nodes[j].size() + (int)nodes[k].size() - 6);
                }
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};

题解 2 - python

• 编辑时间：2023-08-31
• 执行用时：4360ms
• 内存消耗：40.23MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        nodes = [set() for _ in range(n)]
        for [n0, n1] in edges:
            nodes[n0-1].add(n1-1)
            nodes[n1-1].add(n0-1)
        res = inf
        for i in range(n):
            for j in range(i + 1, n):
                if not j in nodes[i]:
                    continue
                for k in range(j + 1, n):
                    if not k in nodes[i] or not k in nodes[j]:
                        continue
                    res = min(res, len(nodes[i]) +
                              len(nodes[j]) + len(nodes[k]) - 6)
        return res if res != inf else -1

题解 3 - rust

• 编辑时间：2023-08-31
• 执行用时：12ms
• 内存消耗：2.24MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_trio_degree(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut nodes = vec![std::collections::HashSet::new(); n];
        for edge in edges {
            let (n0, n1) = (edge[0] as usize - 1, edge[1] as usize - 1);
            nodes[n0].insert(n1);
            nodes[n1].insert(n0);
        }
        let mut res = i32::MAX;
        for i in 0..n {
            for j in i + 1..n {
                if nodes[i].contains(&j) {
                    for k in j + 1..n {
                        if nodes[i].contains(&k) && nodes[j].contains(&k) {
                            res = res
                                .min((nodes[i].len() + nodes[j].len() + nodes[k].len() - 6) as i32)
                        }
                    }
                }
            }
        }
        if res == i32::MAX {
            -1
        } else {
            res
        }
    }
}