在一个社交圈子当中，有 N 个人。每个人都有一个从 0 到 N-1 唯一的 id 编号。
我们有一份日志列表 logs，其中每条记录都包含一个非负整数的时间戳，以及分属两个人的不同 id，logs[i] = [timestamp, id_A, id_B]。
每条日志标识出两个人成为好友的时间，友谊是相互的：如果 A 和 B 是好友，那么 B 和 A 也是好友。
如果 A 是 B 的好友，或者 A 是 B 的好友的好友，那么就可以认为 A 也与 B 熟识。
返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间，就返回 -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 成为好友，大家都互相熟识了。 提示： 1 <= N <= 100 1 <= logs.length <= 10^4 0 <= logs[i][0] <= 10^9 0 <= logs[i][1], logs[i][2] <= N - 1 保证 logs[i][0] 中的所有时间戳都不同 Logs 不一定按某一标准排序 logs[i][1] != logs[i][2]来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-earliest-moment-when-everyone-become-friends 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
参考数据结构：并查集
先按时间排序按时间顺序合并两个人，检查是否只有一个团，如果是，返回当前时间 class dsu { vector<int> f; public: dsu(int n) { f.resize(n); for(int i = 0; i < n; ++i) f[i] = i; } void merge(int a, int b) { int fa = find(a); int fb = find(b); f[fa] = fb; } int find(int a) { int origin = a; while(a != f[a]) a = f[a]; return f[origin] = a; } bool onlyOne() { int count = 0; for(int i = 0; i < f.size(); ++i) { if(i == find(i)) count++; if(count > 1) return false; } return true; } }; class Solution { public: int earliestAcq(vector<vector<int>>& logs, int N) { sort(logs.begin(), logs.end(),[&](auto a, auto b){ return a[0] < b[0]; }); dsu u(N); for(auto& lg : logs) { u.merge(lg[1], lg[2]); if(u.onlyOne()) return lg[0]; } return -1; } };244 ms 32.4 MB
或者，有效的合并 N-1次就完成了 class dsu { vector<int> f; public: dsu(int n) { f.resize(n); for(int i = 0; i < n; ++i) f[i] = i; } void merge(int a, int b) { int fa = find(a); int fb = find(b); f[fa] = fb; } bool weAreFriend(int a, int b) { int fa = find(a); int fb = find(b); return fa == fb; } int find(int a) { int origin = a; while(a != f[a]) a = f[a]; return f[origin] = a; } }; class Solution { public: int earliestAcq(vector<vector<int>>& logs, int N) { sort(logs.begin(), logs.end(),[&](auto a, auto b){ return a[0] < b[0]; }); dsu u(N); for(auto& lg : logs) { if(!u.weAreFriend(lg[1], lg[2])) { //不是朋友时，才进行合并 u.merge(lg[1], lg[2]); N--; if(N==1)//合并了N-1次，找到了 return lg[0]; } } return -1; } };240 ms 32.3 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
