用途

并查集包含合并、查询两种操作，可以接近O(1)的复杂度判断两个元素是否属于同一个集合，通常在最小生成树、查看两个元素是否属于同一个集合(图的连通)、合并集合、集合个数(图的连通分量个数)中均有使用。

模板

int[] p;//并查集

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void union(int x, int y){
    int px = find(x), py = find(y);
    p[px] = py;
}

当然还有带权并查集、秩优化等等，就根据题目适当变通即可。
另：个人习惯将合并方法直接拿出来写在调用的位置; 在初始化时 p[i] = i;