【蓝桥杯】并查集

一.概述

并查集是一种树形数据结构，它主要处理一些不相交集合的合并与查询问题。

每个集合里有很多元素，我们选取其中一个元素作为此集合的代表。

给定一个元素，可以很快找到这个元素所在集合的代表；给定两个元素，判断他们是否处于同一个集合，如果不是，可以将两元素分别所处集合进行合并。

二.实现

用树来表示一个集合，树的每个结点就是集合的一个元素，根节点就是集合的代表。

三.实战演练

//合根植物 并查集
#include <iostream>

using namespace std;

const int N=1e6+10;
int m,n,k;
int p[N];

int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    
    //并查集初始化,所有植物各成一类
    for(int i=1;i<=n*m;i++){
        p[i]=i;
    }
    
    for(int i=1;i<=k;i++){
        int a,b;
        cin>>a>>b;
        int pa=find(a),pb=find(b);
        if(pa!=pb){
            p[pa]=pb;
        }
    }
    int sum=0;
    for(int i=1;i<=n*m;i++){
        if(p[i]==i)
            sum++;
    }
    cout<<sum<<'\n';
    return 0;
}