1101. The Earliest Moment When Everyone Become Friends
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан tableau logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
return самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, return -1.
Exemple:
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.
C# solution
correspondant/originalpublic class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[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 bool Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
}
public class Solution {
public int EarliestAcq(int[][] logs, int n) {
Array.Sort(logs, (a, b) => a[0].CompareTo(b[0]));
var uf = new UnionFind(n);
int groupCount = n;
foreach (var log in logs) {
int timestamp = log[0];
int friendA = log[1];
int friendB = log[2];
if (uf.Union(friendA, friendB)) {
groupCount--;
}
if (groupCount == 1) {
return timestamp;
}
}
return -1;
}
}C++ solution
brouillon automatique, à relire avant soumission#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class UnionFind {
private vector<int>& parent;
private vector<int>& rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[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 bool Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
}
class Solution {
public:
public int EarliestAcq(int[][] logs, int n) {
Array.Sort(logs, (a, b) => a[0].CompareTo(b[0]));
var uf = new UnionFind(n);
int groupCount = n;
foreach (var log in logs) {
int timestamp = log[0];
int friendA = log[1];
int friendB = log[2];
if (uf.Union(friendA, friendB)) {
groupCount--;
}
if (groupCount == 1) {
return timestamp;
}
}
return -1;
}
}Java solution
correspondant/originalclass UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[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 rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
}
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);
int groupCount = n;
for (int[] log : logs) {
int timestamp = log[0];
int friendA = log[1];
int friendB = log[2];
if (uf.union(friendA, friendB)) {
groupCount--;
}
if (groupCount == 1) {
return timestamp;
}
}
return -1;
}
}JavaScript solution
correspondant/originalclass UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i)
this.rank = Array(n).fill(1)
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x])
}
return this.parent[x]
}
union(x, y) {
const rootX = this.find(x)
const rootY = this.find(y)
if (rootX !== rootY) {
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY
} else {
this.parent[rootY] = rootX
this.rank[rootX]++
}
return true
}
return false
}
}
var earliestAcq = function(logs, n) {
logs.sort((a, b) => a[0] - b[0])
const uf = new UnionFind(n)
let groupCount = n
for (const [timestamp, friendA, friendB] of logs) {
if (uf.union(friendA, friendB)) {
groupCount--
}
if (groupCount === 1) {
return timestamp
}
}
return -1
}Python solution
correspondant/originalclass UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * 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):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True
return False
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
logs.sort()
uf = UnionFind(n)
group_count = n
for timestamp, friendA, friendB in logs:
if uf.union(friendA, friendB):
group_count -= 1
if group_count == 1:
return timestamp
return -1Algorithm
Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.
Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.
Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). return этот момент времени.
Если такого момента не существует, return -1.
😎
Vacancies for this task
offres actives with overlapping task tags are affichés.