using System;

using System.Collections.Generic;

​

public class Union {

    public int P {get; private set;}

    public int Q {get; private set;}

    public Union(int p, int q){

        P = p;

        Q = q;

    }

}

​

public class QuickUnion {

    private List<int> _storage;

    public QuickUnion(int capacity){

        _storage = new List<int>(capacity);

        for(int i = 0; i< capacity; i++){

            _storage.Add(i);

        }

    }

    private int Root(int i){

        while(i != _storage[i]){

            i = _storage[i];

        }

        return i;

    }

    public bool Connected(int p, int q){

        return Root(p) == Root(q);

    }

    public void Union(int p, int q){

        if(Connected(p,q)){

            Console.WriteLine("Already Connected");

            return;

        }

        var rootOfP = Root(p);

        var rootOfQ = Root(q);

        _storage[rootOfP] = rootOfQ;

    }

}

​

public class Program {

    public static void Main() {

        var unions = new List<Union> {

            new Union(4, 3),

            new Union(3, 8),

            new Union(6, 5),

            new Union(9, 4),

            new Union(2, 1),

            new Union(8, 9),

            new Union(5, 0),

            new Union(7, 2),

            new Union(6, 1),

            new Union(1, 0),

            new Union(6, 7)

        };

        var n = 10;

        var quickFinder = new QuickUnion(n);

        foreach(var union in unions){

            Console.WriteLine("Connecting p:{0} to q:{1}", union.P, union.Q);

            quickFinder.Union(union.P, union.Q);

        }

        // test

        foreach(var union in unions){

            if(!quickFinder.Connected(union.P, union.Q)){

                Console.WriteLine("Something is messed up.  p:{0} should be connected to q:{1}.", union.P, union.Q);

            }

        }

    }

}