QuickUnionUF.cs

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();
  }
}