关于程序员:PAT并查集模板

const int maxn = 1000;int father[maxn];void init(){//初始化父亲数组    for(int i = 0; i < n; i++){        father[i] = i;    }}int findFather(int a){//查    int x = a;    while(a != father[a])   a = father[a];    while(x != a){//门路压缩        int tmp = father[x];        father[x] = a;        x = tmp;    }    return a;}void Union(int a, int b){//并    int fa = findFather(a);    int fb = findFather(b);    if(fa != fb){//若是题目有要求说序号小的或大的当先人，那么此处能够灵便批改        fa = father[fb];    }}

罕用技巧：

个别会开一个is_root数组来统计并查集的个数。也即遍历所有给定结点，找到其先人，并散列到is_root中，若不让统计个数，则间接置一，否则自增即可。特地的，若要求输入每一个并查集的所有成员，则独自开拓一个member向量数组(vector<node> member[maxn])，并以散列的形式来存储成员信息。