Skip to content

Instantly share code, notes, and snippets.

@dance2die dance2die/QuickUnionUF.cs
Last active May 13, 2017

Embed
What would you like to do?
internal class QuickUnionUF
{
private readonly int[] _id;
private readonly int[] _size;
public QuickUnionUF(int n)
{
_id = new int[n + 1];
_size = new int[n + 1];
for (int i = 0; i < n; i++)
{
_id[i] = i;
_size[i] = 1;
}
}
private int GetRoot(int i)
{
while (i != _id[i])
i = _id[i];
return i;
}
public bool IsConnected(int p, int q)
{
return GetRoot(p) == GetRoot(q);
}
public void Union(int p, int q)
{
int i = GetRoot(p);
int j = GetRoot(q);
if (i == j) return;
if (_size[i] < _size[j])
{
_id[i] = j;
_size[j] += _size[i];
}
else
{
_id[j] = i;
_size[i] += _size[j];
}
}
public int GetMaximumConnectedRoute()
{
return _size.Max();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.