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 Item {

    public int Size {get; set;}

    public int Root {get; set;}

}

​

public class Items {

    private List<Item> _storage;

    public Items(int capacity){

        _storage = new List<Item>(capacity);

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

            var item = new Item { Size = 1, Root = i };

            _storage.Add(item);

        }

    }

    public Item this[int index]{

        get {

            return _storage[index];

        }

    }

}

​

public class WeightedQuickUnion {

    private Items _items;

    public WeightedQuickUnion(int capacity){

        _items = new Items(capacity);

    }

    private int Root(int i){

        while(i != _items[i].Root){

            i = _items[i].Root;

        }

        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;

        }

        // get roots

        var rootOfP = Root(p);

        var rootOfQ = Root(q);

        // get root sizes

        var sizeOfP = _items[rootOfP].Size;

        var sizeOfQ = _items[rootOfQ].Size;

        // always move the smaller tree to the bigger tree

        if(sizeOfP < sizeOfQ){

            _items[rootOfP].Root = rootOfQ; // set p's root to q's root

            _items[rootOfQ].Size += sizeOfP; // add p's size to q's size

        } else {

            _items[rootOfQ].Root = rootOfP; // set q's root to p's root

            _items[rootOfP].Size += sizeOfQ; // add q's size to p's size            

        }

    }

}

​

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

            }

        }

    }

}