Skip to content

3608. Minimum Time for K Connected Components

Description

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:

  • Initially, there is one connected component {0, 1}.
  • At time = 1 or 2, the graph remains unchanged.
  • At time = 3, edge [0, 1] is removed, resulting in k = 2 connected components {0}, {1}. Thus, the answer is 3.

Example 2:

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

Output: 4

Explanation:

  • Initially, there is one connected component {0, 1, 2}.
  • At time = 2, edge [0, 1] is removed, resulting in two connected components {0}, {1, 2}.
  • At time = 4, edge [1, 2] is removed, resulting in k = 3 connected components {0}, {1}, {2}. Thus, the answer is 4.

Example 3:

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

Output: 0

Explanation:

  • Since there are already k = 2 disconnected components {1}, {0, 2}, no edge removal is needed. Thus, the answer is 0.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 105
  • edges[i] = [ui, vi, timei]
  • 0 <= ui, vi < n
  • ui != vi
  • 1 <= timei <= 109
  • 1 <= k <= n
  • There are no duplicate edges.

Solutions

Solution 1: Union-Find

Thinking

After time \(t\), edges with weight greater than \(t\) vanish. Rebuilding the graph for every candidate \(t\) is impossible for \(m\le 10^5\) and weights up to \(10^9\).

Edges only disappear, so the number of components is monotone. Adding edges from largest weight to smallest is time running backwards.

Start with \(n\) components and decrement on each successful union. When the next union would drop below \(k\), the current edge time is the smallest \(t\) that still leaves at least \(k\) components. If the count never falls below \(k\), the answer is \(0\).

We can sort the edges by time in ascending order, then starting from the edge with the largest time, add edges to the graph one by one, while using a union-find data structure to maintain the number of connected components in the current graph. When the number of connected components is less than \(k\), the current time is the minimum time we are looking for.

The time complexity is \(O(n \times \alpha(n))\), and the space complexity is \(O(n)\), where \(\alpha\) is the inverse Ackermann function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
        edges.sort(key=lambda x: x[2])
        uf = UnionFind(n)
        cnt = n
        for u, v, t in edges[::-1]:
            if uf.union(u, v):
                cnt -= 1
                if cnt < k:
                    return t
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class UnionFind {
    private int[] p;
    private int[] size;

    public UnionFind(int n) {
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public boolean union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) {
            return false;
        }

        if (size[pa] > size[pb]) {
            p[pb] = pa;
            size[pa] += size[pb];
        } else {
            p[pa] = pb;
            size[pb] += size[pa];
        }
        return true;
    }
}

class Solution {
    public int minTime(int n, int[][] edges, int k) {
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

        UnionFind uf = new UnionFind(n);
        int cnt = n;

        for (int i = edges.length - 1; i >= 0; i--) {
            int u = edges[i][0];
            int v = edges[i][1];
            int t = edges[i][2];

            if (uf.union(u, v)) {
                if (--cnt < k) {
                    return t;
                }
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class UnionFind {
public:
    vector<int> p;
    vector<int> size;

    UnionFind(int n) {
        p.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    bool unite(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) {
            return false;
        }

        if (size[pa] > size[pb]) {
            p[pb] = pa;
            size[pa] += size[pb];
        } else {
            p[pa] = pb;
            size[pb] += size[pa];
        }
        return true;
    }
};

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, int k) {
        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        UnionFind uf(n);
        int cnt = n;

        for (int i = edges.size() - 1; i >= 0; i--) {
            int u = edges[i][0];
            int v = edges[i][1];
            int t = edges[i][2];

            if (uf.unite(u, v)) {
                cnt--;
                if (cnt < k) {
                    return t;
                }
            }
        }
        return 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
type UnionFind struct {
    p    []int
    size []int
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        p:    make([]int, n),
        size: make([]int, n),
    }
    for i := 0; i < n; i++ {
        uf.p[i] = i
        uf.size[i] = 1
    }
    return uf
}

func (uf *UnionFind) find(x int) int {
    if uf.p[x] != x {
        uf.p[x] = uf.find(uf.p[x])
    }
    return uf.p[x]
}

func (uf *UnionFind) union(a, b int) bool {
    pa := uf.find(a)
    pb := uf.find(b)
    if pa == pb {
        return false
    }

    if uf.size[pa] > uf.size[pb] {
        uf.p[pb] = pa
        uf.size[pa] += uf.size[pb]
    } else {
        uf.p[pa] = pb
        uf.size[pb] += uf.size[pa]
    }
    return true
}

func minTime(n int, edges [][]int, k int) int {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i][2] < edges[j][2]
    })

    uf := NewUnionFind(n)
    cnt := n

    for i := len(edges) - 1; i >= 0; i-- {
        u := edges[i][0]
        v := edges[i][1]
        t := edges[i][2]

        if uf.union(u, v) {
            cnt--
            if cnt < k {
                return t
            }
        }
    }
    return 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class UnionFind {
    p: number[];
    size: number[];

    constructor(n: number) {
        this.p = Array.from({ length: n }, (_, i) => i);
        this.size = Array(n).fill(1);
    }

    find(x: number): number {
        if (this.p[x] !== x) {
            this.p[x] = this.find(this.p[x]);
        }
        return this.p[x];
    }

    union(a: number, b: number): boolean {
        const pa = this.find(a);
        const pb = this.find(b);
        if (pa === pb) return false;

        if (this.size[pa] > this.size[pb]) {
            this.p[pb] = pa;
            this.size[pa] += this.size[pb];
        } else {
            this.p[pa] = pb;
            this.size[pb] += this.size[pa];
        }
        return true;
    }
}

function minTime(n: number, edges: number[][], k: number): number {
    edges.sort((a, b) => a[2] - b[2]);

    const uf = new UnionFind(n);
    let cnt = n;

    for (let i = edges.length - 1; i >= 0; i--) {
        const [u, v, t] = edges[i];

        if (uf.union(u, v)) {
            if (--cnt < k) {
                return t;
            }
        }
    }

    return 0;
}

Comments