列表

详情

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

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

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

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

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

 

示例 1：

输入：n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
输出：3
解释：只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。

示例 2：

输入：n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
输出：0
解释：有 3 个三元组：
1) [1,4,3]，度数为 0 。
2) [2,5,6]，度数为 2 。
3) [5,6,7]，度数为 2 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minTrioDegree(int n, vector<vector<int>>& edges) { } };

java 解法, 执行用时: 236 ms, 内存消耗: 69.5 MB, 提交时间: 2023-08-31 07:54:18 

class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        // 原图
        Set<Integer>[] g = new Set[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new HashSet<Integer>();
        }
        // 定向后的图
        List<Integer>[] h = new List[n];
        for (int i = 0; i < n; ++i) {
            h[i] = new ArrayList<Integer>();
        }
        int[] degree = new int[n];

        for (int[] edge : edges) {
            int x = edge[0] - 1, y = edge[1] - 1;
            g[x].add(y);
            g[y].add(x);
            ++degree[x];
            ++degree[y];
        }
        for (int[] edge : edges) {
            int x = edge[0] - 1, y = edge[1] - 1;
            if (degree[x] < degree[y] || (degree[x] == degree[y] && x < y)) {
                h[x].add(y);
            } else {
                h[y].add(x);
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j : h[i]) {
                for (int k : h[j]) {
                    if (g[i].contains(k)) {
                        ans = Math.min(ans, degree[i] + degree[j] + degree[k] - 6);
                    }
                }
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

golang 解法, 执行用时: 356 ms, 内存消耗: 18.4 MB, 提交时间: 2023-08-31 07:54:00 

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minTrioDegree(n int, edges [][]int) int {
    g := make([]map[int]struct{}, n)
    h := make([][]int, n)
    degree := make([]int, n)
    for i := 0; i < n; i++ {
        g[i] = make(map[int]struct{})
    }

    for _, edge := range edges {
        x, y := edge[0] - 1, edge[1] - 1
        g[x][y], g[y][x] = struct{}{}, struct{}{}
        degree[x]++
        degree[y]++
    }
    for _, edge := range edges {
        x, y := edge[0] - 1, edge[1] - 1
        if degree[x] < degree[y] || (degree[x] == degree[y] && x < y) {
            h[x] = append(h[x], y)
        } else {
            h[y] = append(h[y], x)
        }
    }

    ans := 0x3f3f3f3f
    for i := 0; i < n; i++ {
        for _, j := range h[i] {
            for _, k := range h[j] {
                if _, ok := g[i][k]; ok {
                    ans = min(ans, degree[i] + degree[j] + degree[k] - 6)
                }
            }
        }
    }
    if ans == 0x3f3f3f3f {
        return -1
    }
    return ans
}

python3 解法, 执行用时: 2568 ms, 内存消耗: 42.7 MB, 提交时间: 2023-08-31 07:53:42 

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        # 原图
        g = defaultdict(set)
        # 定向后的图
        h = defaultdict(list)
        degree = [0] * n

        for x, y in edges:
            x, y = x - 1, y - 1
            g[x].add(y)
            g[y].add(x)
            degree[x] += 1
            degree[y] += 1
        
        for x, y in edges:
            x, y = x - 1, y - 1
            if degree[x] < degree[y] or (degree[x] == degree[y] and x < y):
                h[x].append(y)
            else:
                h[y].append(x)
        
        ans = inf
        for i in range(n):
            for j in h[i]:
                for k in h[j]:
                    if k in g[i]:
                        ans = min(ans, degree[i] + degree[j] + degree[k] - 6)

        return -1 if ans == inf else ans

javascript 解法, 执行用时: 444 ms, 内存消耗: 66.6 MB, 提交时间: 2023-08-31 07:53:23 

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var minTrioDegree = function(n, edges) {
    // 原图
    const g = Array(n).fill(0).map(() => new Set());
    // 定向后的图
    const h = Array(n).fill(0).map(() => new Array());
    const degree = Array(n).fill(0);

    for (const [x, y] of edges) {
        g[x - 1].add(y - 1);
        g[y - 1].add(x - 1);
        degree[x - 1]++;
        degree[y - 1]++;
    }
    for (const [x, y] of edges) {
        if (degree[x - 1] < degree[y - 1] || (degree[x - 1] == degree[y - 1] && x < y)) {
            h[x - 1].push(y - 1);
        } else {
            h[y - 1].push(x - 1);
        }
    }

    let ans = Infinity;
    for (let i = 0; i < n; ++i) {
        for (const j of h[i]) {
            for (const k of h[j]) {
                if (g[i].has(k)) {
                    ans = Math.min(ans, degree[i] + degree[j] + degree[k] - 6);
                }
            }
        }
    }

    return ans == Infinity ? -1 : ans;
};

javascript 解法, 执行用时: 168 ms, 内存消耗: 57.2 MB, 提交时间: 2023-08-31 07:53:08 

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var minTrioDegree = function(n, edges) {
    const degree = Array(n).fill(0);
    const g = Array(n).fill(0).map(() => new Array(n).fill(0));

    for (const [x, y] of edges) {
        g[x - 1][y - 1] = g[y - 1][x - 1] = 1;
        degree[x - 1]++;
        degree[y - 1]++;
    }

    let ans = Infinity;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            if (g[i][j] == 1) {
                for (let k = j + 1; k < n; ++k) {
                    if (g[i][k] == 1 && g[j][k] == 1) {
                        ans = Math.min(ans, degree[i] + degree[j] + degree[k] - 6);
                    }
                }
            }
        }
    }
    return ans == Infinity ? -1 : ans;
};

golang 解法, 执行用时: 76 ms, 内存消耗: 14.2 MB, 提交时间: 2023-08-31 07:52:44 

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minTrioDegree(n int, edges [][]int) int {
    g := make([][]int, n)
    degree := make([]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, n)
    }
    for _, edge := range edges {
        x, y := edge[0] - 1, edge[1] - 1
        g[x][y], g[y][x] = 1, 1
        degree[x]++
        degree[y]++
    }
    ans := 0x3f3f3f3f
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if g[i][j] != 1 {
                continue
            }
            for k := j + 1; k < n; k++ {
                if g[i][k] == 1 && g[j][k] == 1 {
                    ans = min(ans, degree[i] + degree[j] + degree[k] - 6)
                }
            }
        }
    }
    if ans == 0x3f3f3f3f {
        return -1
    }
    return ans
}

python3 解法, 执行用时: 2836 ms, 内存消耗: 31 MB, 提交时间: 2023-08-31 07:52:29 

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        g = [[0] * n for _ in range(n)]
        degree = [0] * n
        
        for x, y in edges:
            x, y = x - 1, y - 1
            g[x][y] = g[y][x] = 1
            degree[x] += 1
            degree[y] += 1
        
        ans = inf
        for i in range(n):
            for j in range(i + 1, n):
                if g[i][j] == 1:
                    for k in range(j + 1, n):
                        if g[i][k] == g[j][k] == 1:
                            ans = min(ans, degree[i] + degree[j] + degree[k] - 6)
        
        return -1 if ans == inf else ans

java 解法, 执行用时: 28 ms, 内存消耗: 65.9 MB, 提交时间: 2023-08-31 07:52:16 

class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        int[][] g = new int[n][n];
        int[] degree = new int[n];

        for (int[] edge : edges) {
            int x = edge[0] - 1, y = edge[1] - 1;
            g[x][y] = g[y][x] = 1;
            ++degree[x];
            ++degree[y];
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (g[i][j] == 1) {
                    for (int k = j + 1; k < n; ++k) {
                        if (g[i][k] == 1 && g[j][k] == 1) {
                            ans = Math.min(ans, degree[i] + degree[j] + degree[k] - 6);
                        }
                    }
                }
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

cpp 解法, 执行用时: 304 ms, 内存消耗: 41.6 MB, 提交时间: 2023-08-31 07:52:03 

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n, vector<int>(n));
        vector<int> degree(n);

        for (auto&& edge: edges) {
            int x = edge[0] - 1, y = edge[1] - 1;
            g[x][y] = g[y][x] = 1;
            ++degree[x];
            ++degree[y];
        }

        int ans = INT_MAX;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (g[i][j] == 1) {
                    for (int k = j + 1; k < n; ++k) {
                        if (g[i][k] == 1 && g[j][k] == 1) {
                            ans = min(ans, degree[i] + degree[j] + degree[k] - 6);
                        }
                    }
                }
            }
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

上一题

© 2024 leetcode.cn