怎么做网站排版,佛山免费发布信息的网站,重庆cms建站模板,wordpress 8211基本介绍
并查集主要实现两个操作#xff1a;
合并两个集合查询某个元素的祖宗节点
并查集的两个优化#xff1a;
路径压缩#xff1a; O ( l o g n ) O(logn) O(logn)按秩合并#xff1a; O ( l o g n ) O(logn) O(logn)#xff0c;代码比较复杂#xff0c;一般不单…基本介绍
并查集主要实现两个操作
合并两个集合查询某个元素的祖宗节点
并查集的两个优化
路径压缩 O ( l o g n ) O(logn) O(logn)按秩合并 O ( l o g n ) O(logn) O(logn)代码比较复杂一般不单独用
两种优化结合起来用时间复杂度可以压缩到 O ( α ( n ) ) O(\alpha(n)) O(α(n))
并查集的扩展
并查集在维护两个操作的同时还可以进行以下扩展
记录每个集合大小绑定到根节点上每个点到根节点的距离绑定到每个元素上
格子游戏
题目描述
原题链接
问题分析
形成环等价于两个点在连边之前已经在一个集合里
程序代码
#include iostream
#include algorithm
#include cstringusing namespace std;const int N 40010;
int n, m;
int p[N];// 将二维坐标转换为一维上的点
int get(int x, int y)
{return x * n y;
}int find(int x)
{// 只有祖先节点的p[x]等于自身if( p[x] ! x ) p[x] find(p[x]);return p[x];
}int main()
{cin n m;// 并查集初始化for(int i 0; i n * n; i) p[i] i;int res 0;for(int i 1; i m; i) {int x, y;char c;cin x y c;x--, y--;int a get(x, y);int b;// 向下连一条边if(c D) b get(x 1, y);// 向右连一条边else b get(x, y 1);// 找到所属集合的祖先节点int pa find(a), pb find(b);// 形成环路游戏结束if(pa pb) {res i;break;}// 集合合并p[pa] pb;}if( res ) cout res endl;else cout draw endl;return 0;
}
