并查集的个人理解与使用

￡神魔★判官ぃ 2022-11-01 10:59 89阅读 0赞

> 站在巨人的肩膀上你会看的更远！  
> 每天一个数据结构或算法！

对于并查集的理解你需要看：  
文章一：[https://blog.csdn.net/the\_best\_man/article/details/62416938][https_blog.csdn.net_the_best_man_article_details_62416938]

文章二:[https://blog.csdn.net/jiahuan\_/article/details/112677906][https_blog.csdn.net_jiahuan_article_details_112677906]

# 01.并查集的使用 #

并查集是由一个数组pre\[\]，和两个函数构成的，一个函数为**find()函数**，用于寻找**根节点**的，第二个是**join()函数**，用于合并的。

**初始化**  
我们将每一个结点的父结点设置为自己，如果在**join函数**时未能形成连通，将独立成点。

for(int i=0;i<n;i++)//n表示输入的结点的个数
    { 
        pre[i]=i;//将每一个结点的父节点设置为自己
    }

**find()函数:**

//我们先假设当前组织中最大的是皇上 int find(int x)
    { 
        int r=x;//r记录这个国家中谁是老大 while(pre[r]!=r){ 
        r=pre[r];//找到他的父节点，最终将找到真正的老大
        }
        int i=x,j;//i为需要被压缩的元素（重新认直接上司），j用来保存i原来的直接上司 while(i!=r)//路径压缩算法，如果x的老大不是皇上
        { 
            j=pre[i];//找到x的父节点（老大）
            pre[i]=r;//将x的老大改为皇上
            i=j;//去寻找x原先老大的直接上级（看看是不是皇上）
        }
        return r;//返回当前国家的老大
    }

对于路径压缩算法，可以有很多种，如文章二中提到的将小集合的根节点合并到大集合的根节点。

而这里采用的是所有的人只认根节点，这就好比，皇上说不得行，当兵的只认识将军，没几个认识我，到时候将军反我可咋办，我得去军营里露露脸，让他们知道谁才是老大。  
**递归的方法：**

int find(int k) //寻找k的根结点 
    { 
    	if(pre[k]==k)	return k; //我们以pre的值是否是自身下标来判断根结点 
    	return pre[k]=find(pre[k]); //递归路径压缩 
    }

**join()函数**

void join(int x,int y)
    { 
        int a=find(x);//x的根节点为a
        int b=find(y);//y的根节点为b if(a!=b)//如果a,b不是相同的根节点，则说明a，b不是连通的
        { 
            pre[a]=b;//我们将a，b相连 将a的父结点设置为b
        }
    }

# 02.案例 #

**题目描述**

给出一个并查集，请完成合并和查询操作。
    
    输入格式:
    第一行包含两个整数N、M，表示共有N个元素和M个操作。
    接下来M行，每行包含三个整数Zi、Xi、Yi
    当Zi=1时，将Xi与Yi所在的集合合并
    当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
    
    输出格式:
    如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N
    
    输入样例
    4 7
    2 1 2
    1 1 2
    2 1 2
    1 3 4
    2 1 4
    1 2 3
    2 1 4
    
    输出样例
    N
    Y
    N
    Y
    
    数据规模
    对于30%的数据，N<=10，M<=20；
    
    对于70%的数据，N<=100，M<=1000；
    
    对于100%的数据，N<=10000，M<=200000

代码：

package part1;
    
    import java.util.Scanner;
    
    public class JoinAndFind { 
    	private static int [] pre;//记录每个节点的父节点
    	private static int n;//元素的个数
    	private static int m;//操作的次数
    	public static void main(String[] args) { 
    		int z,x,y;//z什么操作，元素x,y
    		pre = new int[10001];
    		Scanner scan = new Scanner(System.in);
    		n=scan.nextInt();
    		m=scan.nextInt();
    		for(int i=1;i<=n;i++) { //初始化
    			pre[i]=i;
    		}
    		
    		
    		for(int i=1;i<=m;i++) { 
    			z=scan.nextInt();
    			x=scan.nextInt();
    			y=scan.nextInt();
    			if(z==1) { 
    				join(x,y);//合并元素
    			}else { //判断根节点是否相同
    				if(find(x)==find(y)) { 
    					System.out.println("Y");
    				}else { 
    					System.out.println("N");
    				}
    				
    			}
    		}
    	}
    /** * 合并元素 * @param x 要合并的元素1 * @param y 要合并的元素2 */
    	private static void join(int x, int y) { 
    		int a = find(x);//x的根节点
    		int b = find(y);//y的根节点
    		if(a!=b) { //合并
    			pre[a] = b;//将a所在的组织合并到b所在的组织
    		}
    		
    	}
    	/** * 查找元素的根节点 * @param x 要查找的元素 * @return x的根节点 */
    	private static int find(int x) { 
    		if(pre[x]==x) return x;//如果x就是根节点
    		return find(pre[x]);//递归路径压缩
    	}
    }

结果:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]

[https_blog.csdn.net_the_best_man_article_details_62416938]: https://blog.csdn.net/the_best_man/article/details/62416938
[https_blog.csdn.net_jiahuan_article_details_112677906]: https://blog.csdn.net/jiahuan_/article/details/112677906
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70]: /images/20221024/6e878a5cf1344c4e87d18001a2a280d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/2f5c3fc1de4a4446a833f0a9c8ede9c7.png