【图, 并查集】彼此熟识的最早时间

题目

1101. 彼此熟识的最早时间

---

在一个社交圈子当中，有 n 个人。每个人都有一个从 0 到 n - 1 的唯一编号。我们有一份日志列表 logs，其中 logs[i] = [timestampi, xi, yi] 表示 xi 和 yi 将在同一时间 timestampi 成为朋友。

友谊是 相互 的。也就是说，如果 a 和 b 是朋友，那么 b 和 a 也是朋友。同样，如果 a 和 b 是朋友，或者 a 是 b 朋友的朋友 ，那么 a 和 b 是熟识友。

返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间，就返回 -1 。

示例 1：

输入：logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
输出：20190301
解释：
第一次结交发生在 timestamp = 20190101，0 和 1 成为好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp = 20190104，3 和 4 成为好友，社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp = 20190107，2 和 3 成为好友，社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp = 20190211，1 和 5 成为好友，社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp = 20190224，2 和 4 已经是好友了。
第六次结交发生在 timestamp = 20190301，0 和 3 成为好友，大家都互相熟识了。

示例 2:

输入: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
输出: 3

提示：

• 2 <= n <= 100
• 1 <= logs.length <= 10^4
• logs[i].length == 3
• 0 <= timestampi <= 10^9
• 0 <= xi, yi <= n - 1
• xi != yi
• timestampi 中的所有时间戳 均不同
• 所有的对 (xi, yi) 在输入中最多出现一次

解题

方法一：并查集

思路

彼此熟悉的关系看作边，人看作顶点构建出一个无向图，把日志列表按照时间升序排序，维护一个并查集(ds)然后遍历日志数组：

• 合并当前遍历到的日志中的两个顶点。
• 如果当前图的连通分量为 1 说明所有人都互相熟识了，返回当前的时间戳。

如果遍历完成后图的连通分量还没减为 1 则说明图中有人互相还不认识，还没一整个的社交圈子，也就找不到时间戳，返回 -1。

代码

class Solution {
    public int earliestAcq(int[][] logs, int n) {
        Arrays.sort(logs, (a, b) -> a[0] - b[0]);
        DisjointSet ds = new DisjointSet(n);
        for (int[] log : logs) {
            if (!ds.isConnected(log[1], log[2])) {
                ds.union(log[1], log[2]);
                if (ds.groups == 1) return log[0];
            }
        }
        return -1;
    }
}

class DisjointSet {
    public int groups;
    private int[] setArr;

    public DisjointSet(int n) {
        groups = n;
        setArr = new int[groups];
        for (int i = 0; i < groups; i++) setArr[i] = i; 
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            setArr[rootP] = rootQ;
            groups--;
        }
    }
    
    public int find(int n) {
        return n == setArr[n] ? n : (setArr[n] = find(setArr[n]));
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}