【LeetCode（Java） - 1101】彼此熟识的最早时间

1、题目描述

2、解题思路

??经典的并查集算法。

??初始时，有多少个人就有多少个朋友圈，每个圈子的领袖初始时都是每个人自己。

??find 方法：如果 A 所在圈子的领袖不是 A 本身，则继续找 leader[A] 的领袖，直到该圈子的领袖是它自己为止；

??union 方法：如果两个人所在圈子的领袖不是同一个人，则 leader[leaderA] = leaderB，同时圈子个数减一。

3、解题代码

class Solution {
    public int earliestAcq(int[][] logs, int N) {
    Arrays.sort(logs, Comparator.comparingInt(a -> a[0]));Friend f = new Friend(N);for (int[] log : logs) {
    f.union(log[1], log[2]);if (f.circles == 1) {
    return log[0];}}return -1;}class Friend {
    int n;int circles;int[] leader;Friend(int N) {
    n = N;circles = N;leader = new int[n];for (int i = 0; i < leader.length; i++) {
    leader[i] = i;}}int find(int A) {
    while (leader[A] != A) {
    A = leader[A];}return A;}void union(int A, int B) {
    int leaderA = find(A);int leaderB = find(B);if (leaderA != leaderB) {
    leader[leaderA] = leaderB;circles--;}}}
}