1101. The Earliest Moment When Everyone Become Friends

Posted on Edited on In

1101. The Earliest Moment When Everyone Become Friends

Description

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.

Example 1:

1
2
3
4
5
6
7
8
9
Input: 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
Output: 20190301
Explanation:
The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5].
The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5].
The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5].
The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4].
The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens.
The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.

Example 2:

1
2
3
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

Constraints:

  • 2 <= n <= 100
  • 1 <= logs.length <= 10^4
  • logs[i].length == 3
  • 0 <= timestampi <= 10^9
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • All the values timestampi are unique .
  • All the pairs (xi, yi) occur at most one time in the input.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int earliestAcq(vector<vector<int>>& logs, int n) {
        ranges::sort(logs);
        int num_component = n;
        vector<int> roots(n);
        iota(roots.begin(), roots.end(), 0);
        for (auto& log : logs) {
            int x = log[1], y = log[2];
            int rootX = findRoot(x, roots), rootY = findRoot(y, roots);
            if (rootX != rootY) {
                roots[rootX] = rootY;
                if (--num_component == 1) {
                    return log[0];
                }
            }
        }
        return -1;
    }

    int findRoot(int root, vector<int> roots) {
        if (roots[root] != root) {
            roots[root] = findRoot(roots[root], roots);
        }
        return roots[root];
    }
};