侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-24 / 0 评论 / 0 点赞 / 37 阅读 / 787 字 / 正在检测是否收录...

题目

1101. 彼此熟识的最早时间


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

友谊是 相互 的。也就是说,如果 ab 是朋友,那么 ba 也是朋友。同样,如果 ab 是朋友,或者 ab 朋友的朋友 ,那么 ab 是熟识友。

返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间,就返回 -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);
    }
}
0

评论区