Saved from https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

lc1101

class Solution {
    // A typical union-find problem
    // Time: O(nK), where K = tree height
    // Space: O(n)
    public int earliestAcq(int[][] logs, int N) {
        Arrays.sort(logs, (l, r) -> l[0] - r[0]);
        UnionFind uf = new UnionFind(N);
        for (int i = 0; i < logs.length; i++) {
            uf.union(logs[i][1], logs[i][2]);
            if (uf.componentCnt == 1) {
                return logs[i][0];
            }
        }
        return -1;
    }
    
    // Union find algorithm (quick-union version)
    // Time: O(K), where K = tree height
    // Space: O(K), where K = tree height
    public static class UnionFind {
        int componentCnt;
        int[] ids;
        
        public UnionFind(int n) {
            ids = new int[n];
            for (int i = 0; i < n; i++) {
                ids[i] = i;
            }
            componentCnt = n;
        }
        
        public int find(int i) {
            while (ids[i] != i) {
                i = ids[i];
            }
            return i;
        }
        
        public void union(int p, int q) {
            int pid = find(p);
            int qid = find(q);
            if (pid == qid) {
                return;
            }
            ids[pid] = qid;
            componentCnt--;
        }
    }
}