UnionFind implementation The Wikipedia article on the union find problem gives a very simple implementation, which I ported to C# and tested.

I know that the code should be, in the aggregate, asymptotically almost linear. But is it a practical implementation? Are there optimizations I should have used? Is there a way to cut down on the worst-case complexity of single operations?

using System;

/// &lt;summary&gt;
/// A UnionFindNode represents a set of nodes that it is a member of.
/// 
/// You can get the unique representative node of the set a given node is in by using the Find method.
/// Two nodes are in the same set when their Find methods return the same representative.
/// The IsUnionedWith method will check if two nodes' sets are the same (i.e. the nodes have the same representative).
///
/// You can merge the sets two nodes are in by using the Union operation.
/// There is no way to split sets after they have been merged.
/// &lt;/summary&gt;
public class UnionFindNode {
    private UnionFindNode _parent;
    private uint _rank;

    /// &lt;summary&gt;
    /// Creates a new disjoint node, representative of a set containing only the new node.
    /// &lt;/summary&gt;
    public UnionFindNode() {
        _parent = this;
    }

    /// &lt;summary&gt;
    /// Returns the current representative of the set this node is in.
    /// Note that the representative is only accurate untl the next Union operation.
    /// &lt;/summary&gt;
    public UnionFindNode Find() {
        if (!ReferenceEquals(_parent, this)) _parent = _parent.Find();
        return _parent;
    }

    /// &lt;summary&gt;
    /// Determines whether or not this node and the other node are in the same set.
    /// &lt;/summary&gt;
    public bool IsUnionedWith(UnionFindNode other) {
        if (other == null) throw new ArgumentNullException("other");
        return ReferenceEquals(Find(), other.Find());
    }

    /// &lt;summary&gt;
    /// Merges the sets represented by this node and the other node into a single set.
    /// Returns whether or not the nodes were disjoint before the union operation (i.e. if the operation had an effect).
    /// &lt;/summary&gt;
    /// &lt;returns&gt;True when the union had an effect, false when the nodes were already in the same set.&lt;/returns&gt;
    public bool Union(UnionFindNode other) {
        if (other == null) throw new ArgumentNullException("other");
        var root1 = this.Find();
        var root2 = other.Find();
        if (ReferenceEquals(root1, root2)) return false;

        if (root1._rank &lt; root2._rank) {
            root1._parent = root2;
        } else if (root1._rank &gt; root2._rank) {
            root2._parent = root1;
        } else {
            root2._parent = root1;
            root1._rank++;
        }
        return true;
    }
}
If I read the wikipedia article correctly then the algorithm should have amortized constant cost - and you have implemented it pretty much 1:1. Given that with your implementation you always start with disjoint nodes and any call to any of the public methods ends up calling Find which will automatically flatten the tree I doubt you can get much better.
UnionFindNode is not a particularly good name for the data structure: intermingles operations with the data structure in the name. Just Node or maybe DisjointSetNode would be better.
You could use == or != instead of ReferenceEquals which would make the code a bit easier to read.
Consider making your node class generic and add a T value property - right now your nodes are not all that useful as they don't hold any data.