并查集的学习及运用

1.定义

在看并查集之前，我们先来看一下并查集是什么：

并查集是一种用于管理元素所属集合的数据结构。

它也有很多用途：在无向图中找环、判断连个元素是不是一个集合等等，所以用起来也十分方便，代码也很短

2.模板

int find(int k){
	if(vec[k]==k)return k;//判断自己还有没有祖先
	else return vec[k]=find(vec[k]);//找自己的祖先+压缩路径
}
void d(){
	int fx=find(x);//找x的祖先
	int fy=find(y);//找y的祖先
	if(fx!=fy){
		vec[fx]=vec[fy];//合并
	}
	return;
}

这是一个较为常用的模板，也十分的简洁明了，不过在具体的题中有具体的写法，这道题只需把模板扔进去即可。

3.运用

这道修改数组题你会发现不用并查集竟然可以拿很高的分数：

#include<bits/stdc++.h>
using namespace std;
int n,a;bool b[1000007];
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		for(int j=0;b[a];j++){//如果被标记过了，就一直加
			a++;
		}
		b[a]=true;//标记
		printf("%d%c",a,' ');
	}
	return 0;
}

这么easy的代码90分!!!

简直太离谱了，那我们来看一下正解：

先看思路：

我们在找到一个数时，可以直接输出他的祖先，并设置他的祖先+1的祖先的点为新的祖先，意思就是合并他的祖先和他的祖先+1；

拿这一组样例举例：5         2 1 1 3 4

第一次，输出2，合并2，3

第二次，输出1，合并1，2

第三次，输出3，合并3，4

第四次，输出4，合并4，5

 第五次，输出5，合并5，6

代码：

#include<bits/stdc++.h>
using namespace std;
int n,x;
int vec[1000007];
int find(int k){
	if(vec[k]==k)return k;
	else return vec[k]=find(vec[k]);
}
int main() {
	cin>>n;
	for(int i=1;i<=1000007;i++){
		vec[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>x;
		if(x==find(x)){
			cout<<x<<' ';
			vec[x]=x+1;
		}else{
			cout<<find(x)<<' ';
			vec[find(x)]=find(x)+1;
		}
	}
	return 0;
}

这道题如果没有标签其实很难辨认出它是并查集，所以我们要多多观察，仔细看题；

还有一道题叫奶酪，这道题有好几种做法，我分享两种：

并查集：

#include<bits/stdc++.h>
using namespace std;
int f[1001];
int find(int x){
    if (x!=f[x]) f[x]=find(f[x]);
    return f[x];
}
long long dis(long long x,long long y,long long z,long long x1,long long y1,long long z1){
    return (x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1);
}
long long x[100001],y[100001],z[100001];
int f1[100001],f2[100001];
int main(){
    int t;
    scanf("%d",&t);
    int n,h; 
    long long r;
    for (int i=1;i<=t;i++){
        scanf("%d%d%lld",&n,&h,&r);
        int tot1=0;
        int tot2=0;
        for (int j=1;j<=n;j++){
          f[j]=j;
         }
        for (int j=1;j<=n;j++){
            scanf("%lld%lld%lld",&x[j],&y[j],&z[j]);
            if (z[j]+r>=h){
                tot1++;
                f1[tot1]=j;
            }
            if (z[j]-r<=0){
                tot2++;
                f2[tot2]=j;
            }
            for (int k=1;k<=j;k++){
            	if ((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])>4*r*r) continue;
                if (dis(x[j],y[j],z[j],x[k],y[k],z[k])<=4*r*r){
                    int a1=find(j);
                    int a2=find(k);
                    if (a1!=a2) f[a1]=a2;
                }
            }
        }
        int s=0;
        for (int j=1;j<=tot1;j++){
            for (int k=1;k<=tot2;k++){
                if (find(f1[j])==find(f2[k])){
                    s=1; 
                    break;
                }
            }
            if (s==1) break;
        }
        if (s==1) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
} 

BFS：

#include<bits/stdc++.h>
using namespace std;
struct chees {
	long long x, y, z;
};
long long n, h, r, t, k, nk;
chees nl[1007];
bool f[1007], tr;
queue<long long>q;
int main() {
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> n >> h >> r;
		for (int j = 1; j <= n; j++) {
			cin >> nl[j].x >> nl[j].y >> nl[j].z;
		}
		for (int j = 1; j <= n; j++) {
			if (nl[j].z - r <= 0) {
				q.push(j);
				f[j] = true;
				tr = false;
				while (!q.empty()) {
					k = q.front();
					q.pop();
					if (nl[k].z + r >= h) {
						cout << "Yes" << endl;
						tr = true;
						break;
					}
					nk = 1;
					while (nk <= n) {
						if (!f[nk] && sqrt((nl[k].x - nl[nk].x) * (nl[k].x - nl[nk].x) * 1. + (nl[k].y - nl[nk].y) * (nl[k].y - nl[nk].y) * 1.0 + (nl[k].z - nl[nk].z) * (nl[k].z - nl[nk].z) * 1.0) <= 2 * r) {
							q.push(nk);
							f[nk] = true;
						}
						nk++;
					}
				}
				while (!q.empty()) {
					q.pop();
				}
				memset(f, false, sizeof f);
				if(tr){
					break;
				}
			}
		}
		if (!tr) {
			cout << "No" << endl;
		}
		tr=false;
	}
	return 0;
}

还有几道有趣的题目，值得尝试：合根植物、村村通、网络分析。

这里还有其他算法：BFS，DFS；

4.点个赞再走吧