using System.Collections.Generic;

public class UnionFind<T> {

  public class SetElement {
    public SetElement parent;
    public readonly T value;
    public int size; 

    public SetElement(T value) {
      this.value = value;
      parent = this; 
      size = 1; 
    }

    override public string ToString() {
     return string.Format("{0}, size:{1}", value, size);
    }
  }

  Dictionary<T, SetElement> dict;

  public UnionFind() {
    dict = new Dictionary<T, SetElement>(); 
  }

  public SetElement MakeSet(T value) {
    SetElement element = new SetElement(value); 
    dict[value] = element;
    return element;
  }

  public SetElement Find(T value) {
    SetElement element = dict[value];
    SetElement root = element; 
    while(root.parent != root) {
      root = root.parent; 
    }
    SetElement z = element; 
    while(z.parent != z) {
      SetElement temp = z; 
      z = z.parent;
      temp.parent = root;
    }
    return root; 
  }

  public SetElement Union(SetElement root1, SetElement root2) {
    if (root2.size > root1.size) {
      root2.size += root1.size;
      root1.parent = root2;
      return root2;
    } else {
      root1.size += root2.size;
      root2.parent = root1;
      return root1;
    }
  }
}

using System; 
using Pair = System.Collections.Generic.KeyValuePair<string, string>;

public class ConnectedComponents {

  public static void Main() {

    string[] names = {"John", "George", "Paul", "Mick", "Ringo", "Bill", "Brian", "Charlie", "Keith" };
    Pair[] pairs = { new Pair("John", "George"), new Pair("Paul", "Ringo"), new Pair("Ringo", "George"), new Pair("Charlie", "Bill"), new Pair("Keith", "Mick"), new Pair("Brian", "Bill"), new Pair("Charlie", "Keith")}; 
    var UF = new UnionFind<string>(); 

    foreach(var name in names) 
      UF.MakeSet(name);

    foreach(var pair in pairs) {
      if (UF.Find(pair.Key) != UF.Find(pair.Value))
        UF.Union(UF.Find(pair.Key), UF.Find(pair.Value));
    }

    foreach(var name in names) 
      Console.WriteLine("{0} belongs to set {1}", name, UF.Find(name)); 
  }
}

mcs demo/connectedcomponents.cs src/unionfind.cs
mono demo/connectedcomponents.exe

John belongs to set Paul, size:4
George belongs to set Paul, size:4
Paul belongs to set Paul, size:4
Mick belongs to set Charlie, size:5
Ringo belongs to set Paul, size:4
Bill belongs to set Charlie, size:5
Brian belongs to set Charlie, size:5
Charlie belongs to set Charlie, size:5
Keith belongs to set Charlie, size:5

using System; 
using System.Linq; 
using System.Collections.Generic; 

using Cell = System.Collections.Generic.KeyValuePair<int, int>;
using Edge = System.Collections.Generic.KeyValuePair<System.Collections.Generic.KeyValuePair<int, int>, System.Collections.Generic.KeyValuePair<int, int>>;

public class MazeGenerator {

  public static void DrawMaze(List<Edge> edges, int width, int height) {
    Console.WriteLine("\\begin{tikzpicture}[>=latex]");
    Console.WriteLine("  \\draw[thick](0,0) -- ({0},0);",width); 
    Console.WriteLine("  \\draw[thick](0,{0}) -- ({1},{0});",width, height); 
    Console.WriteLine("  \\draw[thick](0,0) -- (0,{0});",height-1);     
    Console.WriteLine("  \\draw[thick]({0},1) -- ({0},{1});",width, height); 
    foreach(var edge in edges) {
      var cell1 = edge.Key;
      var cell2 = edge.Value;
      if (cell1.Value == cell2.Value)
        Console.WriteLine("  \\draw({0},{1}) -- ++(0,1);", cell2.Key, cell1.Value);
      else 
        Console.WriteLine("  \\draw({0},{1}) -- ++(1,0);", cell1.Key, cell2.Value);
    }
    Console.WriteLine("\\end{tikzpicture}");
  }

  public static void Main(string[] args) {

    int width, height;
    if (!(args.Length > 0 && Int32.TryParse(args[0], out width))) width = 7;
    if (!(args.Length > 1 && Int32.TryParse(args[1], out height))) height = width;

    var grid = Enumerable.Range(0, width*height).Select( x => new Cell(x%width,x/width));

    var edges = new List<Edge>();
    var UF = new UnionFind<Cell>(); 
    foreach(var cell in grid) {
      if (cell.Key < width-1) edges.Add(new Edge(cell, new Cell(cell.Key+1, cell.Value)));
      if (cell.Value < height-1) edges.Add(new Edge(cell, new Cell(cell.Key, cell.Value+1)));
      UF.MakeSet(cell);
    }

    var random = new Random();
    var candidates = new List<Edge>(edges);
    int edgesToRemove = grid.Count()-1;
    while(edgesToRemove > 0) {
      int next = random.Next(candidates.Count);
      var edge = candidates[next];
      if (UF.Find(edge.Key) != UF.Find(edge.Value)) {
        UF.Union(UF.Find(edge.Key),UF.Find(edge.Value));
        edges.Remove(edge);
        edgesToRemove--;
      }
      candidates.RemoveAt(next); 
    }
    DrawMaze(edges, width, height); 
  }
}

mcs demo/mazegenerator.cs src/unionfind.cs
mono demo/mazegenerator.exe 7 7

mcs demo/mazegenerator.cs src/unionfind.cs
mono demo/mazegenerator.exe 21 21

mcs demo/mazegenerator.cs src/unionfind.cs
mono demo/mazegenerator.exe 54 54