题解 P3367 【【模板】并查集】

并查集，顾名思义，并是合并，查是查找，集就是集合。 好，那么现在的问题是如何实现并查集，应为我们知道如果真的一个个合并集合，一个个找，肯定会TLE。首先，我们把这些元素想象成一个个点，这些点都是不同的颜色。然后，当我们需要合并的时候，就将所有和$y$一样的颜色染成x的颜色，查找就看$x$和$y$是否是同一颜色。 但是这样查找还是很慢。那么，我们再想：颜色可以用数字表示，而元素则用数组下标表示。那么，我们可以用$f_x$表示x的颜色。再进一步，我们用$f_x$表示x的颜色和哪个元素的颜色相同，合并时只要把$f_y$改成$f_x$就行，因为其他元素在查找过程中会先找到$y$，再找到$x$。 那么，说道这里，基础的东西都讲完了，其他的这么讲也讲不好。具体就看代码注释吧。 ```cpp #include<bits/stdc++.h> using namespace std; int n,m,z,x,y; struct bin { int f[10005]; int lb(int x)//返回x最终要染的颜色 { if(x==f[x]) return x;//如果不用变了，就返回x f[x]=lb(f[x]);//否则继续递归，这是一个名为路径压缩的优化，在代码后面会讲 return f[x]; } void hb(int x,int y)//合并函数 { f[lb(x)]=lb(y);//这里就是把y的最终颜色改成了x的最终颜色 return ; } void cz(int x,int y)//查找函数（声明：函数名和cz没有半点关系） { if(lb(x)==lb(y)) cout<<'Y'<<'\n';//如果x的最终颜色和y的最终颜色相同，就是在一个集合，输出'Y' else cout<<'N'<<'\n'; return ; } }; bin b;//整个结构体就是并查集数据结构 int main() { cin>>n>>m; for(int i=1;i<=n;i++) b.f[i]=i;//每个元素染不同的颜色，依次标号为1号、2号…n号 for(int i=1;i<=m;i++) { cin>>z>>x>>y; if(z==1) b.hb(x,y); else b.cz(x,y); } return 0; } ``` 这里讲一下路径压缩。我们知道，$f_x$是该和什么元素的颜色一样。那么，就不是最终该染颜色。而这样最复杂的情况，就是它形成了一条链，访问链的一端，访问$m$次，要做$n^m$次。结果我不说你也知道。而路径压缩就是把$f_x$变为最终颜色。即$f_x=lb(f_x)$。这样，就算是链访问$m$次，也才做了$n+m-1$次。 # [$\color{red}{\text{结束}}$](https://www.luogu.org/blog/yhdhg1395754790/)