-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path1101-TheEarliestMomentWhenEveryoneBecomeFriends.cs
74 lines (62 loc) · 1.99 KB
/
1101-TheEarliestMomentWhenEveryoneBecomeFriends.cs
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//-----------------------------------------------------------------------------
// Runtime: 144ms
// Memory Usage: 29.3 MB
// Link: https://leetcode.com/submissions/detail/363981633/
//-----------------------------------------------------------------------------
using System.Linq;
namespace LeetCode
{
public class _1101_TheEarliestMomentWhenEveryoneBecomeFriends
{
public int EarliestAcq(int[][] logs, int N)
{
if (logs.Length < N - 1) return -1;
logs = logs.OrderBy(log => log[0]).ToArray();
var uf = new UnionFind(N);
foreach (var item in logs)
{
uf.Union(item[1], item[2]);
if (uf.Count == 1)
return item[0];
}
return -1;
}
private class UnionFind
{
private readonly int[] parents;
private readonly int[] ranks;
public UnionFind(int length)
{
parents = new int[length];
ranks = new int[length];
for (int i = 0; i < length; i++)
parents[i] = i;
Count = length;
}
public int Count { get; set; }
public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);
return parents[index];
}
public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);
if (pIndex1 == pIndex2) return;
if (ranks[pIndex1] > ranks[pIndex2])
{
parents[pIndex2] = pIndex1;
ranks[pIndex2]++;
}
else
{
parents[pIndex1] = pIndex2;
ranks[pIndex1]++;
}
Count--;
}
}
}
}