山东省建设监理协会官方网站,南京响应式网站制作,瑞安 网站建设培训班,农产品期货交易平台app并查集
并查集是一种图形数据结构#xff0c;用于存储图中结点的连通关系。
每个结点有一个父亲#xff0c;可以理解为“一只伸出去的手”#xff0c;会指向另一个点#xff0c;初始时指向自己。一个点的根节点是该点的父亲的父亲的..的父亲#xff0c;直到某个点的父亲…并查集
并查集是一种图形数据结构用于存储图中结点的连通关系。
每个结点有一个父亲可以理解为“一只伸出去的手”会指向另一个点初始时指向自己。一个点的根节点是该点的父亲的父亲的..的父亲直到某个点的父亲是自己根。
当两个点的根相同时我们就说他们时同一类或者是连通的。
如下75136的根都是3所以他们是连通的。
24是连通的而26不连通因为他们的根不同。
找根的方法
如果当前点不是根就返回父亲的根。否则就是自己
用递归的方法实现 int find(int x) { if(pre[x]x)retrun x; return find(pre[x]); } 并查集的合并
在并查集中所有的操作都在根上假如我要使x和y两个点合并我们只需要将find(x)指向find(y)或者find(y)指向find(x);
pre[find(x)]find(y);
假如我们要合并4和6两点我们只需要将2指向3或将3指向2. 路径压缩
找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。
我们可以在找根的过程中将父亲指向根从而实现路径压缩这样可以使得找根的总体时间的复杂度为O(log n)。如下图执行一次root(7)之后沿途的点都会直接指向根3 int find(int x){ return pre[x](pre[x]x?x:find(pre[x]));//当前的这个点是否是根是根的话直接输出x不是根的话去寻中这个根 } 例题
蓝桥幼儿园
题目描述
蓝桥幼儿园的学生是如此的天真无邪以至于对他们来说朋友的朋友就是自己的朋友。
小明是蓝桥幼儿园的老师这天他决定为学生们举办一个交友活动活动规则如下
小明会用红绳连接两名学生被连中的两个学生将成为朋友。
小明想让所有学生都互相成为朋友但是蓝桥幼儿园的学生实在太多了他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你请你帮忙写程序判断某两个学生是否为朋友默认自己和自己也是朋友。
输入描述
第 11 行包含两个正整数N,M其中 N 表示蓝桥幼儿园的学生数量学生的编号分别为1∼N。
之后的第2∼M1 行每行输入三个整数op,x,y
如果 op1表示小明用红绳连接了学生 x 和学生 y 。如果 op2请你回答小明学生 x 和 学生 y 是否为朋友。
输出描述
对于每个op2 的输入如果 x 和 y 是朋友则输出一行 YES否则输出一行 NO。
输入输出样例
示例 1 输入 5 5
2 1 2
1 1 3
2 1 3
1 2 3
2 1 2输出 NO
YES
YES
代码
package chsi;
import java.util.*;
public class chapter1 {static int []pre;//定义一个数组表示每个结点的根是指向谁的public static void main(String[] args) {// TODO Auto-generated method stubScanner scannew Scanner(System.in);int nscan.nextInt();int mscan.nextInt();prenew int[n];//初始化prefor(int i0;in;i) pre[i]i;//初始根都是指向它本身for(int i0;im;i) {int opscan.nextInt();int xscan.nextInt()-1;int yscan.nextInt()-1;if(op1) {union(x,y);}else {xfind(x);yfind(x);if(xy) {System.out.println(YES);}else System.out.println(No);}}}public static int find(int x) {if(pre[x]!x) {pre[x]find(pre[x]);}//表示当前结点不是我们的根节点return pre[x];}//先写一个find查询路径压缩的方式public static void union(int x,int y) {xfind(x);yfind(y);if(x!y) {pre[x]y;}return;}}
