1/**
2 * Union-Find (Disjoint Set Union) data structure with
3 * path compression and union by size optimizations.
4 */
5class UnionFind {
6    // parent[i] holds the parent of node i; if parent[i] == i, then i is a root
7    private int[] parent;
8    // componentSize[i] holds the size of the tree rooted at i (valid only for roots)
9    private int[] componentSize;
10
11    /**
12     * Initializes n disjoint sets, each containing a single element.
13     *
14     * @param n the number of elements
15     */
16    public UnionFind(int n) {
17        parent = new int[n];
18        componentSize = new int[n];
19        for (int i = 0; i < n; i++) {
20            parent[i] = i;          // each node is initially its own parent (root)
21            componentSize[i] = 1;   // each component starts with size 1
22        }
23    }
24
25    /**
26     * Finds the representative (root) of the set containing x,
27     * applying path compression to flatten the tree.
28     *
29     * @param x the element to find
30     * @return the root of the set containing x
31     */
32    public int find(int x) {
33        if (parent[x] != x) {
34            // recursively find the root and compress the path
35            parent[x] = find(parent[x]);
36        }
37        return parent[x];
38    }
39
40    /**
41     * Merges the sets containing a and b using union by size.
42     *
43     * @param a the first element
44     * @param b the second element
45     * @return true if a merge occurred, false if they were already connected
46     */
47    public boolean union(int a, int b) {
48        int rootA = find(a);
49        int rootB = find(b);
50
51        // already in the same set, nothing to merge
52        if (rootA == rootB) {
53            return false;
54        }
55
56        // attach the smaller tree under the larger one to keep depth small
57        if (componentSize[rootA] > componentSize[rootB]) {
58            parent[rootB] = rootA;
59            componentSize[rootA] += componentSize[rootB];
60        } else {
61            parent[rootA] = rootB;
62            componentSize[rootB] += componentSize[rootA];
63        }
64        return true;
65    }
66}
67
68class Solution {
69    /**
70     * Determines the minimum edge weight (time) such that, after keeping only
71     * the edges processed so far (from largest weight downward), the graph is
72     * split into at least k connected components.
73     *
74     * @param n     the number of nodes
75     * @param edges the edges, where each edge is [u, v, time]
76     * @param k     the target number of connected components
77     * @return the answer time value, or 0 if it is never reached
78     */
79    public int minTime(int n, int[][] edges, int k) {
80        // sort edges by weight in ascending order
81        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
82
83        UnionFind unionFind = new UnionFind(n);
84        // initially every node is its own component
85        int componentCount = n;
86
87        // iterate from the largest-weight edge down to the smallest
88        for (int i = edges.length - 1; i >= 0; i--) {
89            int u = edges[i][0];
90            int v = edges[i][1];
91            int time = edges[i][2];
92
93            // if this edge connects two previously separate components,
94            // merging them reduces the total component count by one
95            if (unionFind.union(u, v)) {
96                // once the component count drops below k, the current
97                // edge's time is the minimum satisfying value
98                if (--componentCount < k) {
99                    return time;
100                }
101            }
102        }
103
104        // the target component count was never crossed
105        return 0;
106    }
107}
108

1class UnionFind {
2public:
3    // parent[i] stores the representative (root) of the set that i belongs to
4    vector<int> parent;
5    // setSize[i] stores the size of the set rooted at i (only valid for roots)
6    vector<int> setSize;
7
8    // Initialize n disjoint sets, each element is its own parent
9    UnionFind(int n) {
10        parent.resize(n);
11        setSize.resize(n, 1);
12        for (int i = 0; i < n; i++) {
13            parent[i] = i;
14        }
15    }
16
17    // Find the root of x with path compression
18    int find(int x) {
19        if (parent[x] != x) {
20            parent[x] = find(parent[x]);  // Flatten the tree for future queries
21        }
22        return parent[x];
23    }
24
25    // Union the sets containing a and b using union by size
26    // Returns true if a merge happened, false if they were already connected
27    bool unite(int a, int b) {
28        int rootA = find(a);
29        int rootB = find(b);
30        if (rootA == rootB) {
31            return false;  // Already in the same set
32        }
33
34        // Attach the smaller tree under the larger one to keep trees shallow
35        if (setSize[rootA] > setSize[rootB]) {
36            parent[rootB] = rootA;
37            setSize[rootA] += setSize[rootB];
38        } else {
39            parent[rootA] = rootB;
40            setSize[rootB] += setSize[rootA];
41        }
42        return true;
43    }
44};
45
46class Solution {
47public:
48    int minTime(int n, vector<vector<int>>& edges, int k) {
49        // Sort edges by their time/weight in ascending order
50        sort(edges.begin(), edges.end(),
51             [](const vector<int>& a, const vector<int>& b) {
52                 return a[2] < b[2];
53             });
54
55        UnionFind uf(n);
56        int componentCount = n;  // Initially every node is its own component
57
58        // Iterate from the largest weight edge down to the smallest.
59        // By adding edges from heaviest to lightest, the answer is the weight
60        // of the edge that first makes the number of components drop below k.
61        for (int i = static_cast<int>(edges.size()) - 1; i >= 0; i--) {
62            int u = edges[i][0];
63            int v = edges[i][1];
64            int time = edges[i][2];
65
66            // Only merging distinct components reduces the component count
67            if (uf.unite(u, v)) {
68                componentCount--;
69                if (componentCount < k) {
70                    // This edge's time is the minimum required answer
71                    return time;
72                }
73            }
74        }
75
76        // Already satisfied the component requirement without removing any edge
77        return 0;
78    }
79};
80

1// Parent array for the disjoint set (each node's representative)
2let p: number[] = [];
3// Size array tracking the number of nodes in each component
4let size: number[] = [];
5
6// Find the root of x with path compression
7function find(x: number): number {
8    if (p[x] !== x) {
9        p[x] = find(p[x]);
10    }
11    return p[x];
12}
13
14// Merge the sets containing a and b using union by size.
15// Returns false if they are already connected, true otherwise.
16function union(a: number, b: number): boolean {
17    const pa = find(a);
18    const pb = find(b);
19    // Already in the same component, nothing to merge
20    if (pa === pb) return false;
21
22    // Attach the smaller tree under the larger one
23    if (size[pa] > size[pb]) {
24        p[pb] = pa;
25        size[pa] += size[pb];
26    } else {
27        p[pa] = pb;
28        size[pb] += size[pa];
29    }
30    return true;
31}
32
33function minTime(n: number, edges: number[][], k: number): number {
34    // Sort edges by their time/weight in ascending order
35    edges.sort((a, b) => a[2] - b[2]);
36
37    // Initialize the disjoint set: every node is its own parent with size 1
38    p = Array.from({ length: n }, (_, i) => i);
39    size = Array(n).fill(1);
40
41    // cnt tracks the current number of connected components
42    let cnt = n;
43
44    // Iterate edges from largest weight to smallest.
45    // By adding heavier edges first, we keep components merging;
46    // the moment the component count drops below k, the current
47    // edge's time is the answer (the minimum time to reach >= k components
48    // by removing edges with time >= t).
49    for (let i = edges.length - 1; i >= 0; i--) {
50        const [u, v, t] = edges[i];
51
52        // Merge the two endpoints; if a real merge happens, decrement count
53        if (union(u, v)) {
54            if (--cnt < k) {
55                return t;
56            }
57        }
58    }
59
60    // All nodes merged without reaching the threshold below k
61    return 0;
62}
63