并查集

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 100005;

int father[MAX]; // 节点的父节点

void init() // 初始化
{
    for(int i = 0; i < MAX; i++) father[i] = i; //每个节点构成一个只有该节点的集，彼此无联系
}

int finds_r(int x) // 递归形式的父节点查找
{
    if(father[x] != x) father[x] = finds_r(father[x]); // 并查集的路径压缩，使所有该链上的节点指向唯一父节点
    return father[x];
}

int finds_l(int x) // 循环形式的查找
{
    int f, pf;
    f = x;
    while(x != father[x]) x = father[x];// 找到最终的父节点
    while(f != x)
    {
        pf = father[f];
        father[f] = x; // 更新路径上所有节点的父节点信息
        f = pf;
    }
    return x;
}

int unions(int x, int y) // 合并x,y所在的集
{
    int p = finds_l(x);
    int q = finds_r(y); // 找到x,y的最终父节点
    if(p != q) father[p] = q; // 将p所在集的所有节点并入q所在集中
}