并查集

并查集是一种用于处理一些不相交集合（Disjoint Sets）的合并及查询问题的树形数据结构,可以高效的解决多个元素的集合应用问题中：

合并集合、查询某元素属于某集合的问题

并查集的基本函数：

初始化：

void init()//未进行操作时没一个元素的祖先的是他自己
{
    for (int i = 1; i <= n; i++)
        f[i] = i;
}

查找：

int find(int x)//如果还没有查找到根节点（f[x]==x）
{               //就不断递归查找x的祖先的祖先（f[x]=find(find[x])）
    return f[x] == x ? x : f[x] = find(f[x]);
}

合并：

void merge(int a, int b)
{
    int x = find(a);
    int y = find(y);
    if (x != y)
        f[y] = x;
}

基础并查集：

例题：洛谷 P1551 亲戚

#include<iostream>
using namespace std;
const int maxn = 100010;
int n, m, p, f[maxn];
void init()
{
    for (int i = 1; i <= n; i++)
        f[i] = i;
}
int find(int x)
{
    return f[x] == x ? x : find(f[x]);
}
void merge(int a, int b)
{
    int x = find(a);
    int y = find(b);
    if (x != y)
        f[y] = x;
}
int main()
{
    cin >> n >> m >> p;
    init();
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }
    for (int i = 1; i <= p; i++)
    {
        int a, b;
        cin >> a >> b;
        if (find(a) == find(b))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

 拓展并查集：

例题：洛谷 P1525 关押罪犯

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
struct people
{
    int u, v, w;
}p[100010];
int f[100010];
int e[100010];
bool cmp(people a, people b)
{
    return a.w > b.w;
}
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int a, int b)
{
    int x = find(a);
    int y = find(b);
    if (x != y)
        f[y] = x;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= m; i++)
        cin >> p[i].u >> p[i].v >> p[i].w;
    sort(p + 1, p + 1 + m, cmp);
    for (int i = 1; i <= m; i++)
    {
        int a = p[i].u;
        int b = p[i].v;
        if (find(a) == find(b))
        {
            cout << p[i].w << endl;
            return 0;
        }
        else
        {
            if (!e[a])
            {
                e[a] = b;
            }
            else
            {
                merge(e[a], b);
            }
            if (!e[b])
            {
                e[b] = a;
            }
            else
            {
                merge(e[b], a);
            }
        }
    }
    cout << 0 << endl;
    return 0;
}

 特殊的并查集：

例题：P2024 [NOI2001]食物链

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn = 100010;
int n, m;
int ans;
int f[maxn * 3];
void init()
{
    for (int i = 1; i <= n * 3; i++)
        f[i] = i;
}
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int a, int b)
{
    int x = find(a);
    int y = find(b);
    if (x != y)
        f[y] = x;
}
int main()
{
    cin >> n >> m;
    init();
    for(int i=1;i<=m;i++)
    {
        int t, x, y;
        cin >> t >> x >> y;
        if (x > n || y > n)
        {
            ans++;
            continue;
        }
        if (t == 1)
        {
            if (find(x) == find(y + n) || find(x + n) == find(y))
            {
                ans++;
            }
            else
            {
                merge(x, y);
                merge(x + n, y + n);
                merge(x + 2 * n, y + 2 * n);
            }
        }
        else
        {
            if (find(x) == find(y) || find(x) == find(y + n))
            {
                ans++;
            }
            else
            {
                merge(x + n, y);
                merge(x + 2 * n, y + n);
                merge(x, y + 2 * n);
            }
        }
    }
    cout << ans << endl;
    return 0;
}