There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi.
Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a 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. If there is no such earliest time, return -1.
Solution
这里我们使用并查集。在此之前，先将其按照时间顺序进行排序，如果属于不同根的，则合并的时候返回 \(1\)，意思是减少了一个。当最后剩下一个时，答案就是此刻的时间。
点击查看代码
class Solution {
private:
vector<int> fa, sz;
int find(int x){
if(x==fa[x]) return x;
return fa[x] = find(fa[x]);
}
int joint(int x, int y){
int fax = find(x), fay = find(y);
// same root
if(fax==fay)return 0;
if(sz[fax]<sz[fay]){
fa[fax] = fay;
sz[fay]=max(sz[fay], 1+sz[fax]);
}
else{
fa[fay]=fax;
sz[fax] = max(sz[fax], 1+sz[fay]);
}
return 1;
}
static bool cmp(vector<int>&log1, vector<int>&log2){
return log1[0]<log2[0];
}
public:
int earliestAcq(vector<vector<int>>& logs, int n) {
sort(logs.begin(), logs.end(), cmp);
int tot=n;
fa = vector<int>(n); sz = vector<int>(n,1);
for(int i=0;i<n;i++)fa[i]=i;
for(auto ele:logs){
tot-=(joint(ele[1], ele[2]));
if(tot==1) return ele[0];
}
return -1;
}
};