Use the path compression weighted union find algorithm. See Algorithms 4th edition for the detailed description.

```
public class Solution {
public int LongestConsecutive(int[] nums) {
UnionFind uf = new UnionFind(nums.Length);
var dict = new Dictionary<int, int>(); // nums[i] -> i
for(int i = 0; i < nums.Length; i++) {
if(dict.ContainsKey(nums[i])) {
continue;
} else {
dict.Add(nums[i], i);
if(dict.ContainsKey(nums[i] - 1)) {
uf.Union(i, dict[nums[i] - 1]);
}
if(dict.ContainsKey(nums[i] + 1)) {
uf.Union(i, dict[nums[i] + 1]);
}
}
}
return uf.MaxSize;
}
private class UnionFind
{
private int[] parent;
private int[] size;
public UnionFind(int n) {
parent = new int[n];
size = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
MaxSize = 1;
}
public int MaxSize { get; private set; }
public void Union(int p, int q) {
int rootP = Find(p);
int rootQ = Find(q);
if(rootP == rootQ) return;
if(size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
MaxSize = Math.Max(MaxSize, size[rootQ]);
} else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
MaxSize = Math.Max(MaxSize, size[rootP]);
}
}
private int Find(int p) {
int root = p;
while(parent[root] != root) {
root = parent[root];
}
while(parent[p] != root) {
int newP = parent[p];
parent[p] = root;
p = newP;
}
return root;
}
}
```

}