并查集

建立具有联通关系的集合的数据结构；什么是连通性：A->B, B->C， 则A->C。ABC就可以划在一个具有联通关系的集合中。

基础结构是father数组

int father[MAXN];

void init(int n) {
    for(int i = 0; i < n; i++) {
        father[i] = i;
    }
}

void find(int x) {
    return father[x] == x ? x : father[x] = find(father[x]);
}

void join(int x, int y) {搜索
    x = find(x);
    y = find(y);
    if (x != y) {
        father[x] = y;
    }
}

在数组中，根的数量就是并查集的数量。