1101. The Earliest Moment When Everyone Become Friends

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.

class Solution {
    vector<int> g;
    int find(int n) {
        return g[n] == n ? n : g[n] = find(g[n]);
    }
public:
    int earliestAcq(vector<vector<int>>& logs, int n) {
        sort(logs.begin(), logs.end());
        g = vector<int>(n);
        for(int i = 0; i < n; i++) g[i] = i;
        int res = 0;
        for(auto log : logs) {
            int pa = find(log[1]), pb = find(log[2]);
            if(pa == pb) continue;
            res = log[0];
            g[pa] = g[pb] = min(pa,pb);
        }
        
        int allFriend = 0;
        for(int i = 0; i < n and !allFriend; i++) {
            allFriend += find(i);
        }
        return !allFriend ? res : -1;
    }
};