Medium

题目描述

给你一个整数 n 和一个有 n 个节点的无向图，节点标号从 0 到 n - 1。图用二维数组 edges 表示，其中 edges[i] = [ui, vi, timei] 表示节点 ui 和 vi 之间有一条无向边，该边可以在时间 timei 被移除。

同时给你一个整数 k。

最初，图可能是连通的也可能是不连通的。你的任务是找到最小的时间 t，使得在移除所有时间 <= t 的边后，图包含至少 k 个连通分量。

返回最小时间 t。

连通分量是图的一个子图，其中任意两个顶点之间都存在路径，且该子图的顶点不与子图外的顶点共享边。

示例 1：

输入：n = 2, edges = [[0,1,3]], k = 2
输出：3
解释：
- 最初，有一个连通分量 {0, 1}
- 在时间 = 1 或 2 时，图保持不变
- 在时间 = 3 时，边 [0, 1] 被移除，产生 k = 2 个连通分量 {0}, {1}
因此答案是 3

示例 2：

输入：n = 3, edges = [[0,1,2],[1,2,4]], k = 3
输出：4
解释：
- 最初，有一个连通分量 {0, 1, 2}
- 在时间 = 2 时，边 [0, 1] 被移除，产生两个连通分量 {0}, {1, 2}
- 在时间 = 4 时，边 [1, 2] 被移除，产生 k = 3 个连通分量 {0}, {1}, {2}
因此答案是 4

示例 3：

输入：n = 3, edges = [[0,2,5]], k = 2
输出：0
解释：
因为已经有 k = 2 个不连通的分量 {1}, {0, 2}，所以不需要移除任何边
因此答案是 0

提示：

  • 1 <= n <= 10^5
  • 0 <= edges.length <= 10^5
  • edges[i] = [ui, vi, timei]
  • 0 <= ui, vi < n
  • ui != vi
  • 1 <= timei <= 10^9
  • 1 <= k <= n
  • 没有重复的边

解题思路

这道题的核心思路是使用二分搜索和并查集来解决。

问题分析：

  • 我们需要找到最小的时间 t，使得移除所有时间 <= t 的边后，图至少有 k 个连通分量
  • 随着时间 t 的增加，被移除的边越来越多，连通分量的数量也会增加
  • 这具有单调性，适合用二分搜索

解题步骤：

  1. 首先检查初始状态是否已经满足条件（连通分量 >= k）
  2. 如果不满足，使用二分搜索在所有边的时间值中找到最小的 t
  3. 对于每个候选时间 t，使用并查集计算移除时间 <= t 的边后的连通分量数量
  4. 如果连通分量数量 >= k，说明当前时间可行，尝试更小的时间；否则需要更大的时间

具体实现：

  • 使用并查集来高效地维护和查询连通分量
  • 二分搜索的范围是所有边的时间值
  • 对于每次检查，重新构建并查集，只添加时间 > t 的边

代码实现

class Solution {
private:
    class UnionFind {
    public:
        vector<int> parent;
        int components;
        
        UnionFind(int n) : parent(n), components(n) {
            iota(parent.begin(), parent.end(), 0);
        }
        
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        void unite(int x, int y) {
            int px = find(x), py = find(y);
            if (px != py) {
                parent[px] = py;
                components--;
            }
        }
        
        int getComponents() {
            return components;
        }
    };
    
    int countComponents(int n, vector<vector<int>>& edges, int maxTime) {
        UnionFind uf(n);
        for (auto& edge : edges) {
            if (edge[2] > maxTime) {
                uf.unite(edge[0], edge[1]);
            }
        }
        return uf.getComponents();
    }
    
public:
    int minTime(int n, vector<vector<int>>& edges, int k) {
        if (countComponents(n, edges, -1) >= k) {
            return 0;
        }
        
        vector<int> times;
        for (auto& edge : edges) {
            times.push_back(edge[2]);
        }
        sort(times.begin(), times.end());
        times.erase(unique(times.begin(), times.end()), times.end());
        
        int left = 0, right = times.size() - 1, result = times.back();
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (countComponents(n, edges, times[mid]) >= k) {
                result = times[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
        def find(parent, x):
            if parent[x] != x:
                parent[x] = find(parent, parent[x])
            return parent[x]
        
        def union(parent, x, y):
            px, py = find(parent, x), find(parent, y)
            if px != py:
                parent[px] = py
                return True
            return False
        
        def count_components(max_time):
            parent = list(range(n))
            components = n
            for u, v, t in edges:
                if t > max_time and union(parent, u, v):
                    components -= 1
            return components
        
        # Check if already have k components
        if count_components(-1) >= k:
            return 0
        
        # Get all unique times and binary search
        times = sorted(set(edge[2] for edge in edges))
        
        left, right = 0, len(times) - 1
        result = times[-1]
        
        while left <= right:
            mid = (left + right) // 2
            if count_components(times[mid]) >= k:
                result = times[mid]
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    private class UnionFind {
        private int[] parent;
        public int Components { get; private set; }
        
        public UnionFind(int n) {
            parent = new int[n];
            Components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        public void Union(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px != py) {
                parent[px] = py;
                Components--;
            }
        }
    }
    
    private int CountComponents(int n, int[][] edges, int maxTime) {
        var uf = new UnionFind(n);
        foreach (var edge in edges) {
            if (edge[2] > maxTime) {
                uf.Union(edge[0], edge[1]);
            }
        }
        return uf.Components;
    }
    
    public int MinTime(int n, int[][] edges, int k) {
        if (CountComponents(n, edges, -1) >= k) {
            return 0;
        }
        
        var times = edges.Select(e => e[2]).Distinct().OrderBy(x => x).ToArray();
        
        int left = 0, right = times.Length - 1, result = times[^1];
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CountComponents(n, edges, times[mid]) >= k) {
                result = times[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

var minTime = function(n, edges, k) {
    function find(parent, x) {
        if (parent[x] !== x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
    
    function union(parent, x, y) {
        const px = find(parent, x);
        const py = find(parent, y);
        if (px !== py) {
            parent[px] = py;
            return true;
        }
        return false;
    }
    
    function countComponents(maxTime) {
        const parent = Array.from({length: n}, (_, i) => i);
        let components = n;
        for (const [u, v, t] of edges) {
            if (t > maxTime && union(parent, u, v)) {
                components--;
            }
        }
        return components;
    }
    
    // Check if already have k components
    if (countComponents(-1) >= k) {
        return 0;
    }
    
    // Get all unique times and binary search
    const times = [...new Set(edges.map(edge => edge[2]))].sort((a, b) => a - b);
    
    let left = 0, right = times.length - 1;
    let result = times[times.length - 1];
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (countComponents(times[mid]) >= k) {
            result = times[mid];
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(E log E + E log E × α(n))其中 E 是边的数量，排序需要 O(E log E)，二分搜索进行 O(log E) 次，每次需要 O(E × α(n)) 时间进行并查集操作
空间复杂度O(n + E)并查集需要 O(n) 空间，存储时间数组需要 O(E) 空间