假设在一个社会群体中，有N个不同的人，其唯一的id从0到N-1。在这里，我们有一个日志列表，其中每个日志[i] = [time，id_A，id_B]包含一个非负整数时间戳记，以及两个不同人员的ID。每个日志都显示两个不同的人成为朋友的时间。如果A是与B的朋友，那么B是与A的朋友。如果A是与B的朋友，或者A是与B认识的人的朋友，那么假设A的人与B了结。我们必须找到最早的时间每个人都结识了其他人。如果没有找到这样的时间，则返回-1。因此，如果输入类似于：[[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。这是因为第一个事件发生在时间戳= 20190101，并且在人0和1成为朋友之后，我们有了友谊组[0,1]，[2]，[3]，[4]，[5]。然后第二个事件发生在时间戳= 20190104，并且在第3个人和第4个人成为朋友之后，我们具有以下友谊组[0,1]，[2]，[3,4]，[5]。此后，第三个事件在时间戳= 20190107发生，并且在人2和3成为朋友之后，我们具有以下友谊组[0,1]，[2,3,4]，[5]。然后第四个事件发生在时间戳= 20190211，并且在第1个人和第5个人成为朋友之后，我们具有以下友谊组[0,1,5]，[2,3,4]。在第五个事件在时间戳= 20190224发生之后，由于2和4人已经是朋友，所以发生了任何事情。最后，
为了解决这个问题，我们将遵循以下步骤-
定义一个名为find()的方法，它的值将为x，其工作方式如下-
如果父母[x]为-1，则返回x
父母[x]：=查找（父母[x]）
回父母[x]
在主要方法中，它将按以下方式工作：
定义两个数组，称为父级和等级，大小为N，用-1填充父级，用1填充等级
排序日志
对于日志中的每个元素-
对i [1]和i [2]执行合并
find（i [2]）和find（i [1]）
如果N在等级数组中，则返回i [0]
返回-1
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int N) {
vector<int> ds (N, -1);
sort(begin(logs), end(logs));
for(vector<int> &k : logs) {
if(un(k[1], k[2], ds) == N) return k[0];
}
return -1;
}
int un(int u, int v, vector<int> & ds) {
u = find(u, ds);
v = find(v, ds);
if(u != v) {
ds[v] += ds[u];
ds[u] = v;
}
return -ds[v];
}
int find(int u, vector<int> & ds) {
return ds[u] < 0? u : ds[u] = find(ds[u], ds);
}
};
main(){
vector<vector<int>> v = {
{20190101,0,1},{20190104,3,4},{20190107,2,3},{20190211,1,5},
{20190224,2,4},{20190301,0,3},{20190312,1,2},{20190322,4,5}
};
Solution ob;
cout <<ob.earliestAcq(v, 6);
}[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5], [20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]] 6
输出结果
20190301