算法竞赛模板 并查集

①基础并查集算法

#define MAX 100005
int p[MAX];
int find(int r)
{
    if(p[r]!=r)
        p[r]=find(p[r]);
    return p[r];
}
void join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)p[fx]=fy;
}
void init()
{
    for(int i=1;i<=MAX;i++)
        p[i]=i;
}

---

②并查集加秩数组算法（计算每个家族里的总人数）

#define MAX 100005
int p[MAX],rank[MAX]; 
int find(int r)
{
    if(p[r]!=r)
        p[r]=find(p[r]);
    return p[r];
}
void join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
    {
        p[fx]=fy;
        rank[fy]+=rank[fx];
        rank[fx]=0;
    }
}
void init()
{
    for(int i=1;i<=MAX;i++)
        p[i]=i;
}