并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。

一，对并查集的认识
并查集是树形结构，常常在题目中用来判断两个元素是否属于同一个集合，每个集合都有一个特征性元素称为这个集合的father，如果两个元素的father相同，则说明这两个元素属于同一集合,若这两个元素的father不相同，则说明这两个元素不属于一个集合。并查集就是这样一种支持合并和查询的树形数据结构。在题目中的应用有，判断两个点是否属于同一个联通块，最小生成树kruskal算法中，判断加边是否会有环等。
在考察并查集的题目中，一般我们用一个f数组来实现并查集的功能，起初所有的f[i]=i;证明所有元素都是单独一个集合。

//并查集初始化
for(int i=1;i<=n;i++) f[i]=i;

二，并查集的基本操作
1，并查集的合并操作（merge）
简而言之，就是将两个元素所在的集合合并成一个集合，操作简单，首先我们只需要找到两个集合的特征性元素，然后把其中一个特征性元素变成另一个，这样两个集合特征性元素相同，两个集合就合并在了一起，在merge操作中我们运用到了按秩合并来优化。

inline void merge(int f1,int f2)
{
f[f1]=f2;
return; }//普通合并

按秩合并：所谓秩就是树高，按秩合并就是按照秩序合并，起初我们给每个点赋高为一，以后在每次合并的过程中，都用树高小的指向树高大的，这样可以保证树高不超过log2N,把查询的最坏复杂度从O(n)减小到O(logn)。

inline void merge(int x,int y)
{
    int f1=find(x);
    int f2=find(y);
    if(f1!=f2)
    {
        if(rank[x]<=rank[y]) f[f1]=f2,rank[y]=max(rank[y],rank[x]+1);
        else f[f2]=f1,rank[x]=max(rank[x],rank[y]);
    }
    return;}     

2,并查集的查询操作
就是查询两个元素是否属于同一个集合，首先我们要先找到这两个元素所在集合的特征性元素。如果两个特征性元素相同，则两个元素属于同一个集合，否则属于两个集合，其中我们用到路径压缩来优化，路径压缩就是在查询过程中，从此节点到根节点路径上的所有节点的f全部改为根节点，这样在下次查询时，就可以减少递归过程从而达到优化的目的。

inline int find(int k)
{
    if(f[k]==k) return f[k];
    return f[k]=find(f[k]);
}

*:按秩合并和路径压缩不可以同时使用，一般我们使用路径压缩来优化。

并查集完整代码（洛谷P3367）

#include<cstdio>
#include<iostream>

using namespace std;

int n,m,f[10005];

int find(int k)
{
    if(f[k]==k) return f[k];
    return f[k]=find(f[k]);
}

void merge(int x,int y)
{
    int f1=find(x);
    int f2=find(y);
    if(f1!=f2) f[f1]=f2;
    return;
} 

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int xi,yi,zi;
        scanf("%d%d%d",&zi,&xi,&yi);
        if(zi==1) merge(xi,yi);
        else if(zi==2) 
        {
            int f1=find(xi);
            int f2=find(yi);
            if(f1==f2) printf("Y\n");
            else printf("N\n");
        } 
    }
    return 0;
}

祝各位OIER NOIP2019 RP++ SCORE++

并查集

原文：https://www.cnblogs.com/Hoyoak/p/11336653.html