并查集入门

许久未写博客了，最近在学习数据结构，为了巩固自身记忆以及深入细节，还是打算继续写下去

并查集 字面意思就是把很多集合并为一个起到查找降低复杂度的作用

核心操作：p【数字或者映射或者集合】= 集合

理解思路：

1.一开始每个数字（映射）都是自己一个集合 p[ i ] = i

2.当做出合并操作 （ p[x]=p[y] ) 时有几种理解

（1）把一个元素放到一个集合里 p【元素】=集合

（2）把这个集合放到另一个集合里 p 【集合】=集合

3.若多次做出上述操作（2）时，需要更新原集合的元素到新集合（降低复杂度为o(1) ），通过find函数在每次查找的同时更新集合

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

例 AcWing 1250. 格子游戏1250. 格子游戏 - AcWing题库

题目大意 给出n*n的点阵 ，两个人能将点阵相邻两点连线，当连成封闭图形的时候，游戏结束

分析题意，当连线的两点已经相连的时候成环，简化为操作的两个点位于一个集合（相连）的时候游戏结束

用一维数组简化图形 （x，y）变成（x*n+y） 注意：x和y都要从0开始（其实不从0开始也行，想想为什么）

题目不难，这里直接给出ac代码：

#include<bits/stdc++.h>
using namespace std;
int p[400010];
int n,m;
int get(int x,int y){
	return x*n+y;
}
int find(int x){
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}

int main(){
	cin>>n>>m;
	int ans=0;
	for(int i=0;i<n*n;i++){
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		char op;
		cin>>x>>y>>op;
		x--;y--;
		int a=get(x,y),b;
		if(op=='D') b=get(x+1,y);
		else b=get(x,y+1);
		int pa=find(a),pb=find(b);
		
		if(pa==pb&&!ans){
			ans=i;
		}
		
		p[pa]=pb;
		
	}
	if(ans==0)cout<<"draw"<<endl;
	else cout<<ans<<endl;
}

不从0开始的话 就保证唯一映射的同时注意初始化要覆盖

for(int i=0;i<201*201;i++)p[i]=i;

总结一下写并查集题的优势：字少，写多了有成就感