LeetCode-in-Java

3608. Minimum Time for K Connected Components

Medium

You are given an integer n and an undirected graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, timei] indicates an undirected edge between nodes ui and vi that can be removed at timei.

You are also given an integer k.

Initially, the graph may be connected or disconnected. Your task is to find the minimum time t such that after removing all edges with time <= t, the graph contains at least k connected components.

Return the minimum time t.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

Example 1:

Input: n = 2, edges = [[0,1,3]], k = 2

Output: 3

Explanation:

Example 2:

Input: n = 3, edges = [[0,1,2],[1,2,4]], k = 3

Output: 4

Explanation:

Example 3:

Input: n = 3, edges = [[0,2,5]], k = 2

Output: 0

Explanation:

Constraints:

Solution

public class Solution {
    public int minTime(int n, int[][] edges, int k) {
        int maxTime = 0;
        for (int[] e : edges) {
            if (e[2] > maxTime) {
                maxTime = e[2];
            }
        }
        int lo = 0;
        int hi = maxTime;
        int ans = maxTime;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (countComponents(n, edges, mid) >= k) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }

    private int countComponents(int n, int[][] edges, int t) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int comps = n;
        for (int[] e : edges) {
            if (e[2] > t) {
                int u = find(parent, e[0]);
                int v = find(parent, e[1]);
                if (u != v) {
                    parent[v] = u;
                    comps--;
                }
            }
        }
        return comps;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}