做爰全过程免费的视网站频,成品视频直播软件推荐哪个好一点非周马加,网站建设的空间是什么,用jsp做的网站首页文章目录 1.并查集操作的简单实现2.解决问题3. 并查集优化3.1 合并的优化3.2查询优化3.3查询优化2 通常用“帮派”的例子来说明并查集的应用背景#xff1a;在一个城市中有 n ( n 1 0 6 ) n(n 10^6) n(n106)个人#xff0c;他们分成不同的帮派#xff0c;给出… 文章目录 1.并查集操作的简单实现2.解决问题3. 并查集优化3.1 合并的优化3.2查询优化3.3查询优化2 通常用“帮派”的例子来说明并查集的应用背景在一个城市中有 n ( n 1 0 6 ) n(n 10^6) n(n106)个人他们分成不同的帮派给出一些人的关系例如 1 1 1号、 2 2 2号是朋友 1 1 1号、 3 3 3号也是朋友那么他们都属于一个帮派。在分析完所有的朋友关系之后问有多少帮派每人属于哪个帮派。 这个数据量应该是不能用暴力的办法求解那我们应该怎么办呢 由此我们引出一种新的数据结构并查集
1.并查集操作的简单实现
初始化: 定义数组 i n t s [ ] int\ s[\ ] int s[ ] 是以结点 i i i 为元素的并查集在开始的时候还没有处理点与点之间的朋友关系所以每个点属于独立的集并且以元素 i i i 的值表示它的集 s [ i ] s[ i ] s[i]例如元素 1 1 1的集 s [ 1 ] 1 s[1]1 s[1]1。所示为图解左边给出了元素与集合的值右边画出了逻辑关系。为了便于讲解左边区分了结点 i i i 和集 s s s (把集的编号加上了下画线)右边用圆圈表示集方块表示元素。 合并(1): 例如加入第 1 个朋友关系 ( 1 , 2 ) (1,2) (1,2)如下图所示。在并查集s中把结点 1 合 并到结点 2也就是把结点 1 的集 1 改成结点 2 的集 2 。合并(2): 加入第 2 2 2 个朋友关系 ( 1 , 3 ) (1,3) (1,3)如下图所示。查找结点 1 1 1 的集是 2 2 2 ,再递归查找元素 2 2 2 的集是 2 2 2 ,然后把元素 2 2 2 的集 2 2 2 合并到结点 3 3 3 的集 3 3 3 。此时结点 1 1 1、 2 2 2、 3 3 3属于一个集。在图中为了简化图示把元素 2 2 2 和集 2 2 2 画在了一起。 合并(3) 加入第 3 3 3 个朋友关系 ( 2 , 4 ) (2,4) (2,4), 如图所示。 查找 在上面步骤中已经有查找操作。查找元素的集是一个递归的过程直到元素的值和它的集相等就找到了根结点的集。从上面的图中可以看到这棵搜索树的高度可能很大复杂度是 O ( n ) O_{(n)} O(n)的变成了一个链表出现了树的“退化”现象。统计有多少个集: 如果 s [ i ] i s[ i ] i s[i]i这是一个根结点是它所在的集的代表。统计根结点的数量就是集的数量。
2.解决问题
有 n n n 个人一起吃饭有些人互相认识。认识的人想坐在一起不想跟陌生人坐。例如 A A A 认识 B B B B B B 认识 C C C那么 A A A、 B B B、 C C C会坐在一张桌子上。给出认识的人的关系问需要多少张桌子。
我们可以根据上文的描述得到如下并查集代码
#includebits/stdc.h
using namespace std;
const int N 1007;
int f[N]; //并查集void init(){ //初始化for(int i 1; i N; i){f[i] i;}
}int find_father(int x){ //找自己的集if(f[x] x)return x;else return find_father(f[x]);
}void union_set(int x, int y){ //合并x find_father(x);y find_father(y);if(x ! y)f[x] f[y];
}
int main(){init();int n, m, x, y;cin n m;for(int i 1; i m; i){cin x y;union_set(x, y);}int cnt 0; //记录集的数量for(int i 1; i n; i){if(f[i] i){cnt ;}}cout cnt;return 0;
}在上述程序中查找、合并、的搜索深度是树的长度复杂度都是 O ( n ) O_{(n)} O(n)性能比较差。下面介绍合并和查找的优化方法优化之后查找和合并的复杂度都小于 O ( l o g 2 n ) O(log_2n) O(log2n)。
3. 并查集优化
3.1 合并的优化
在合并元素 x x x和 y y y时先搜到它们的根结点然后再合并这两个根结点即把一个根结点的集改成另一个根结点。这两个根结点的高度不同如果把高度较小的集合并到较大的集上能减少树的高度。下面是优化后的代码在初始化时用 h e i g h t [ i ] height[i] height[i] 定义元素 i i i 的高度在合并时一同更改。
int high[N];
void init(){ //初始化for(int i 1; i N; i){f[i] i;high[i] 0;}
}
void union_set(int x, int y){ //优化合并x find_father(x);y find_father(y);if(high[x] high[y]){high[x];f[y] x;}else{if(high[x] high[y]){f[x] y;}else{f[y] x;}}
}3.2查询优化
在上面的查询程序 f i n d f a t h e r ( ) find_father() findfather() 中查询元素 i i i 所属的集需要搜索路径找到根结点返回 的结果是根结点。这条搜索路径可能很长。如果在返回的时候顺便把 i i i 所属的集改成根结 点如图所示那么下次再搜的时候就能在 O ( 1 ) O_{(1)} O(1) 的时间内得到结果。
int find_father(int x){ //优化的查询 if(f[x] ! x)f[x] find_father(f[x]); return f[x];
}这个方法称为路径压缩因为在递归过程中整个搜索路径上的元素从元素 i i i 到根结点的所有元素所属的集都被改为根结点。路径压缩不仅优化了下次查询而且优化了合并因为在合并时也用到了查询。
3.3查询优化2
上面的代码用递归实现如果数据规模太大担心爆栈可以用下面的非递归代码
int find_father(int x) {int r x;while (f[r] ! r)r f[r]; //找到根的位置int i x, j;while(i ! r){j f[i];f[i] r; //把路径的根统一i j;}return r;
}
