免费个人网站源码php,网络运营商是干嘛的,无形资产 网站建设,前端网站开发的公用头部并查集#xff08;并茶几#xff09;的应用
一、What‘s that#xff1f; 并查集是一种树型的数据结构#xff0c;用于处理一些不相交集合#xff08;Disjoint Sets#xff09;的合并及查询问题。常常在使用中以森林来表示。 ——百度百科 二、How to uphold
0.我们的需…并查集并茶几的应用
一、What‘s that 并查集是一种树型的数据结构用于处理一些不相交集合Disjoint Sets的合并及查询问题。常常在使用中以森林来表示。 ——百度百科 二、How to uphold
0.我们的需求
一开始我们拥有一个集族集合的集合集族中所有集合不相交每个集合有且仅有一个元素。 百度百科告诉我们 并查集至少需要支持两种操作
1.合并某两个集合a,b。
2.询问两个元素x,y是否属于同一集合。
1.可行的想法
我们能够想到用树的结构存储这样一个集合每一次的合并就相当于将其中一棵树的根的父亲改为另一子树的根的编号。
记录一个值f[i]表示i的父亲结点当i为根时将父亲视为自己也就是f[i]i。 所以我们有一个性质若f[i]i则i为此树的根。 初始时所有的点的f[i]i。
2.初始化
void init(){ for (int i1;in;i) f[i]i; } 3.查找树根
那么如何寻找一个结点所在的树的根呢 Q只要沿着f[i]一直向上跳到f[i]i此时的i结点便是树根
int find(int x){ return f[x]x?x:find(f[x]);}
//1.如果f[x]x返回树根为x; 2.如果f[x]!x继续搜索x的祖先f[x]是否为树根 维护合并
接下来维护集合的合并操作。 例如我们需要合并2和6所在的集合 那么只需要将2子树的根结点1结点与6子树的根结点5结点连接即可 void Union(int x,int y)
{int xxfind(x),yyfind(y); //找到两树的根 if (xx!yy) { f[yy]xx; } //如果两树的根不同合并两棵树
}5.优化原始并茶几
这就是并查集的“初始版本”了。 但我们发现它每一次的询问时间复杂度可能达到O(n)。 因为当数据退化为一条链的时候每一次对链尾的find的次数是O(size)
a.按秩合并
所以这样一个数据结构在我们看来并不优尝试着优化。 我们发现一棵较高的树x与一棵较低的树y合并时应该从较高的树向较低的树连边使其合并。是为按秩合并。f[y]x
void Union(int x,int y)
{int xxfind(x),yyfind(y); if (xx!yy) { if (rank[xx]rank[yy]) f[yy]xx; //按秩合并rank[xx]表示xx树的高度 else f[xx]yy; }
}这一优化据说能将时间复杂度降低为O(logn)
b.路径压缩
还有一个更简单且高效的优化路径压缩。 我们发现我们并不需要知道我们如何沿着f[i]向上跳我们只需要找到最终的root就能够完成任务了。所以我们把f[i]的定义改为记录i的祖先结点的编号在我们每一次find树根的时候更新f[i]的值为树根如此一来当我们再次find(i)时就能一步找到树根的位置。
int find(int x){ return f[x](f[x]x?x:find(f[x])); }
//将得到的值直接赋予f[x]即可 这样路径压缩优化过后每一次find时间复杂度理论上为O(1)union的时间也是O(1)这样我们就完成了一个能够维护部分集合操作的优秀数据结构。 一般情况下路径压缩后的时间复杂度已经能达到O(1)所以通常不会写较为麻烦的按秩合并so以下的所有代码舍弃按秩合并的优化。
三、How to use it
并查集是一个短小精悍的数据结构因此在各类竞赛中的出现频率还是比较高的并查集也有一些巧妙的思路与方法。
一般的并查集能够维护
子树内信息。通常在树根上维护从子结点到根的信息。
1.首先来一道裸题亲戚
问题描述 若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。 规定 x和y是亲戚y和z是亲戚那么x和z也是亲戚。如果x,y是亲戚那么x的亲戚都是y的亲戚y的亲戚也都是x的亲戚。
数据输入 第一行三个整数n,m,pn5000,m5000,p5000分别表示有n个人m个亲戚关系询问p对亲戚关系。 以下m行每行两个数MiMj1MiMjN表示Ai和Bi具有亲戚关系。 接下来p行每行两个数PiPj询问Pi和Pj是否具有亲戚关系。 数据输出 P行每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系 样例 input 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 output Yes Yes No
solution
一题并查集裸题只是为了演示整体代码。明显只是维护集合的合并询问结点连通性。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int INF0x3f3f3f3f;//1061109567
const int MAXN20005;
/*--------------------------------------------------------------------*/
//请省略以上部分int f[MAXN];
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)c-0; cgetchar(); }return x*f;
}
int find(int x){ return f[x](f[x]x?x:find(f[x])); }
void Union(int x,int y)
{int xxfind(x),yyfind(y); if (xx!yy) f[xx]yy;
}
void init(int n){ for (int i1;in;i) f[i]i; }
int main()
{int nread(),mread(),Caseread();init(n);for (int i1;im;i){int xread(),yread();Union(x,y);}while (Case--){int xread(),yread();if (find(x)find(y)) puts(Yes);else puts(No);}return 0;
}
2.一道稍稍不同的题POJ1988 Cube Staking
Description Farmer John and Betsy are playing a game with N (1 N 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1 P 100,000) operation. There are two types of operations: moves and counts.
In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
Input
Line 1: A single integer, PLines 2…P1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a ‘M’ for a move operation or a ‘C’ for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.
Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
Output Print the output from each of the count operations in the same order as the input file.
Sample Input 6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4
Sample Output 1 0 2 Source USACO 2004 U S Open
Solution
题意 有两种操作
将一堆立方体x堆在另一堆立方体y上面。询问x下面有多少个立方体。
这一题需要维护两个额外的信息
r[i]表示从i结点到根节点一共有多少结点i到根的距离1num[i]表示子树一共有多少结点。
只需要稍稍更改find的过程即可。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int INF0x3f3f3f3f;//1061109567
const int MAXN30005;
/*--------------------------------------------------------------------*/
//请省略以上部分int f[MAXN1],r[MAXN1],num[MAXN1];
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)c-0; cgetchar(); }return x*f;
}
inline char readc()
{char cgetchar();while (!isalnum(c)) cgetchar();return c;
}
inline int find(int x)
{if (f[x]x) return x;int tmpf[x];f[x]find(f[x]);r[x]r[tmp];return f[x];
}
int main()
{int Caseread();for (int i1;iMAXN;i) f[i]i,num[i]1,r[i]0;for (int i1;iCase;i){char creadc();if (cM){int xread(),yread();int xxfind(x),yyfind(y);if (xx!yy){f[yy]xx;r[yy]num[xx];num[xx]num[yy];}}else {int xread();int xxfind(x);printf(%d\n,num[xx]-r[x]-1);}} return 0;
}本文总结
以上是一些并查集的简单应用但也是一些精妙并查集技巧操作的基础。
若已经熟练掌握这些基础那么可以学习一些其他更精妙并查集的方法
并查集的结点删除带权并查集偏移向量、补集应用 Ps名字很多 并查集的扩展域
这些内容以后博主会慢慢补充。
