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]),并以散列的形式来存储成员信息。