并查集

typedef struct {
    ElementType Data;
    int Parent; // 双亲表示法
} SetType;

int Find(SetType S[], ElementType X) {
    int i;
    for (i = 0; i < MaxSize && S[i].Data != X; ++ i);
    if (i == MaxSize) return -1;
    for (; S[i].Parent >= 0; i = S[i].Parent);
    return i;
}

void Union(SetType S[], ElementType X1, ElementType X2) {
    int Root1 = Find(S, X1);
    int Root2 = Find(S, X2);
    if (Root1 != Root2)
        if (S[Root1].Parent <= S[Root2].Parent) {
            S[Root1].Parent += S[Root2].Parent;
            S[Root2].Parent = Root1;
        } else {
            S[Root2].Parent += S[Root1].Parent;
            S[Root1].Parent = Root2;
        }
}