并查集

概念

并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。（维基百科）

并查集一般有三个操作

• 1.初始化（init）
• 2.查询（Find）
• 3.合并（Union）、

1. 初始化

我们用 par 数组表示i结点的父亲，rank数组表示树的高度，当par[x] = x 时，x就是所在树的根，因为刚开始没有边，每个结点就是自己的根。

void init(int n)
{
    for(int i = 0; i < n; i++)
    {
        par[i] = i;
        rank[i] = 0;
    }
}

2. 查询

查询树的根
写法1（递归）

int find( int x)
{
    if(par[x] == x)
        return x;
    else
        return par[x] = find( par[x]);//路径压缩
}

写法2

int find(int x)
{
    int root, temp;
    root = x;
    while(root != par[root])//查找位置
        root = par[root];
    while(x != root)//路径压缩
    {
        temp = par[x];
        par[temp] = root;
        x = temp;
    }
    return root;
}

3.合并

void union(int x,int y)//合并x,y所在集合
{
    x = find(x);
    y = find(y);
    if(x == y)//判断x,y是否属于同一集合
        return ;
    //防止树退化（辉哥说用了很多年从来发现有明显优化的现象发生。。。）
    if(rank[x] < rank[y])
        par[x] = y;
    else
    { 
        par[y] = x;
        if(rank[x] == rank[y])
            rank[x]++;
    }
}

并查集全家桶

例题1 poj 1182 食物链

题意：
有三种关系 A吃B B吃C C吃A
有N个动物 编号1~N，属于A B C的一类。1<=N<=50000
给出两种信息共K条 0<=K<=100000
1.x，y同类
2.x 吃 y
请你判断说假话的总数。

例题2 poj 1611 The Suspects

题意：0号学生染病，有n个学生（0到n-1），m个小组。和0号学生同组的学生染病，病可以传染。
输入格式：n,m
数量 学生编号（m行）

例题3 poj 1988 Cube Stacking

题意：n个方块（n<=30000）,p组操作（p<=100000）,操作有两种，M a b 将含有a的堆放在包含b的堆上，还有一种是 C a统计a下面有多少个方块

思路：带权并查集，一堆中最顶上的方块作为父节点，用dist[X] 统计X到父亲节点的距离，rank[par[X]]表示团的大小，两者相减即为答案

并查集的应用

1.Krusakal算法中加边时判断边的两点是不是在同一个连通分量上
2.判环