You are given an integer n representing n people labeled from 0 to n - 1. You are also given a list of logs, where each log is a list of three integers [timestamp, x, y] indicating that person x and person y became friends at time timestamp. Friendship is transitive: If a is friends with b and b is friends with c, then a is also friends with c.
Return the earliest timestamp at which everyone became friends (i.e., all people are connected). If there is no such moment, return -1.
x and y.-1.To solve this problem, we need to determine when all people become part of a single connected group, given a series of friendship events. A brute-force approach would be to simulate the network for every event and check connectivity each time, but this would be inefficient.
The core insight is that this problem is about finding when a group of people becomes "fully connected" through a sequence of pairwise connections. This is similar to the classic "union-find" or "disjoint set" problem in computer science, where we efficiently track connected components as we merge sets.
Instead of checking the entire network at each step, we can use a union-find data structure to track the number of connected components. Each time two separate groups merge, the total number of groups decreases by one. When only one group remains, everyone is connected.
Here’s how we can solve the problem step by step:
n, where each person is initially their own parent.n).[timestamp, x, y], perform a union operation between x and y.timestamp as the answer.-1.We use union-find because it allows us to efficiently merge groups and check connectivity in nearly constant time.
Suppose n = 4 and the logs are:
[20190101, 0, 1][20190104, 3, 4][20190107, 2, 3][20190211, 1, 3][20190224, 0, 2][20190301, 0, 3][20190312, 1, 2]20190211.We stop as soon as all are connected.
O(mn) per event, where m is the number of logs and n is the number of people.O(m^2 n), which is inefficient.O(m \log m)O(1) per union with path compression (inverse Ackermann function), so O(m) total.O(m \log m) time, O(n) space for the union-find structure.The problem asks for the earliest moment that all people are connected by friendship, given a set of pairwise logs. By modeling the problem as a dynamic connectivity scenario, we efficiently track merging groups using the union-find data structure. Sorting the logs ensures chronological processing, and each union brings us closer to the fully connected state. The solution is both elegant and efficient, leveraging classic algorithms for dynamic connectivity.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1]*n
self.count = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
self.parent[px] = py
elif self.rank[px] > self.rank[py]:
self.parent[py] = px
else:
self.parent[py] = px
self.rank[px] += 1
self.count -= 1
return True
class Solution:
def earliestAcq(self, logs, n):
logs.sort()
uf = UnionFind(n)
for time, x, y in logs:
uf.union(x, y)
if uf.count == 1:
return time
return -1
class UnionFind {
public:
vector<int> parent, rank;
int count;
UnionFind(int n) : parent(n), rank(n, 1), count(n) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
count--;
return true;
}
};
class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int n) {
sort(logs.begin(), logs.end());
UnionFind uf(n);
for (auto& log : logs) {
int time = log[0], x = log[1], y = log[2];
uf.unite(x, y);
if (uf.count == 1) return time;
}
return -1;
}
};
class UnionFind {
int[] parent, rank;
int count;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;
for (int i = 0; i < n; ++i) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
public boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
count--;
return true;
}
}
class Solution {
public int earliestAcq(int[][] logs, int n) {
Arrays.sort(logs, (a, b) -> Integer.compare(a[0], b[0]));
UnionFind uf = new UnionFind(n);
for (int[] log : logs) {
int time = log[0], x = log[1], y = log[2];
uf.union(x, y);
if (uf.count == 1) return time;
}
return -1;
}
}
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = Array(n).fill(1);
this.count = n;
}
find(x) {
if (this.parent[x] !== x)
this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
let px = this.find(x), py = this.find(y);
if (px === py) return false;
if (this.rank[px] < this.rank[py]) {
this.parent[px] = py;
} else if (this.rank[px] > this.rank[py]) {
this.parent[py] = px;
} else {
this.parent[py] = px;
this.rank[px]++;
}
this.count--;
return true;
}
}
var earliestAcq = function(logs, n) {
logs.sort((a, b) => a[0] - b[0]);
let uf = new UnionFind(n);
for (let [time, x, y] of logs) {
uf.union(x, y);
if (uf.count === 1) return time;
}
return -1;
};