LeetCode 1101. 彼此熟识的最早时间（排序+并查集）

示例：
输入：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]

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;
    }
};

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;
    }
};