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

    private List<int> _storage;

    public QuickFind(int capacity){

        _storage = new List<int>(capacity);

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

            _storage.Add(i);

        }

    }

    public bool Connected(int p, int q){

        return _storage[p] == _storage[q];

    }

    public void Union(int p, int q){

        if(Connected(p,q)){

            Console.WriteLine("Already Connected");

            return;

        }

        var pid = _storage[p];

        var qid = _storage[q];

        for(int i = 0; i < _storage.Count; i++){

            if(_storage[i] == pid){

                _storage[i] = qid;

            }

        }

    }

}

​

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

            }

        }

    }

}