原题链接在这里：https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

题目：

In a social group, there are N people, with unique integer ids from 0 to N-1.

We have a list of logs, where each logs[i] = [timestamp, id_A, id_B] contains a non-negative integer timestamp, and the ids of two different people.

Each log represents the time in which two different people became friends.  Friendship is symmetric: if A is friends with B, then B is friends with A.

Let's say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B.

Return the earliest time for which every person became acquainted with every other person. Return -1 if there is no such earliest time.

 

Example 1:

Input: 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
Output: 20190301
Explanation: 
The first event occurs at timestamp = 20190101 and after 0 and 1 become friends we have the following friendship groups [0,1], [2], [3], [4], [5].
The second event occurs at timestamp = 20190104 and after 3 and 4 become friends we have the following friendship groups [0,1], [2], [3,4], [5].
The third event occurs at timestamp = 20190107 and after 2 and 3 become friends we have the following friendship groups [0,1], [2,3,4], [5].
The fourth event occurs at timestamp = 20190211 and after 1 and 5 become friends we have the following friendship groups [0,1,5], [2,3,4].
The fifth event occurs at timestamp = 20190224 and as 2 and 4 are already friend anything happens.
The sixth event occurs at timestamp = 20190301 and after 0 and 3 become friends we have that all become friends.

Note:

1. 1 <= N <= 100
2. 1 <= logs.length <= 10^4
3. 0 <= logs[i][0] <= 10^9
4. 0 <= logs[i][1], logs[i][2] <= N - 1
5. It's guaranteed that all timestamps in logs[i][0] are different.
6. Logs are not necessarily ordered by some criteria.
7. logs[i][1] != logs[i][2]

题解：

If log[1] and log[2] do NOT have same ancestor, put them into same union. 

When count of unions become 1, that is the first time all people become friends and output time.

Time Complexity: O(mlogN). m = logs.length. find takes O(logN). With path compression and union by weight, amatorize O(1).

Space: O(N).

AC Java:

 1 class Solution {
 2     public int earliestAcq(int[][] logs, int N) {
 3         UF uf= new UF(N);
 4         Arrays.sort(logs, (a, b)-> a[0]-b[0]);
 5         
 6         for(int [] log : logs){
 7             if(uf.find(log[1]) != uf.find(log[2])){
 8                 uf.union(log[1], log[2]);   
 9             }
10             
11             if(uf.count == 1){
12                 return log[0];
13             }
14         }
15         
16         return -1;
17     }
18 }
19 
20 class UF{
21     int [] parent;
22     int [] size;
23     int count;
24     
25     public UF(int n){
26         this.parent = new int[n];
27         this.size = new int[n];
28         for(int i = 0; i<n; i++){
29             parent[i] = i;
30             size[i] = 1;
31         }
32         
33         this.count = n;
34     }
35     
36     public int find(int i){
37         while(i != parent[i]){
38             parent[i] = parent[parent[i]];
39             i = parent[i];
40         }
41         
42         return parent[i];
43     }
44     
45     public void union(int p, int q){
46         int i = find(p);
47         int j = find(q);
48         if(size[i] > size[j]){
49             parent[j] = i;
50             size[i] += size[j];
51         }else{
52             parent[i] = j;
53             size[j] += size[i];
54         }
55         
56         this.count--;
57     }
58 }

类似Friend Circles.