一文看明白并查集

用户10604450

发布于 2024-03-15 14:31:39

750

发布于 2024-03-15 14:31:39

文章被收录于专栏：练习两年半练习两年半

什么是并查集？

并查集本质就是集合。

并查集可以进行集合合并的操作（并）
并查集可以查找元素在哪个集合中（查）
并查集维护的是一堆集合（集）

对于并查集我们需要知道两个信息

元素的值
集合的标号

用什么样的数据结构表示并查集？

我们能不能让一个数组存储每个节点的父节点，连成一棵树呢？

初始时每个节点都是一个单独的集合，父节点指向自己，

如果要合并两个集合，那么将a的父节点设为b，将a插入到b节点下充当子节点

那么如何判断是否是同一集合呢？就看祖宗节点是否相同，如果相同则代表是同一集合

初始化：

int []p=new int[N];   //存储每个节点的父节点
for (int i = 1; i <=n; i++)  p[i]=i;

返回x的祖宗节点:

    public static int find(int x){
        if(p[x]!=x)  
      p[x]=find(p[x]); //将x的父亲置为x父亲的祖先节点,实现路径的压缩
        return p[x];
    }

find的功能是用于查找祖先节点，那么路径压缩又是怎么完成的

合并为同一集合：

 p[find(a)] = find(b);

查找是否同一集合

find(a) == find(b)

如果想知道每一个集合的数量呢？

我们引入一个size集合，存储每个节点自己的数量+子孙节点的数量，

那么祖宗节点的size就是整个集合的数量，即size[find(a)]

初始化：

  for (int i = 1; i <=n; i++) {
            p[i]=i;
            size[i]=1;
   }

合并为同一集合：

 p[find(a)] = find(b);
 size[find(b)]+=size[find(a)]

给一个例题连通块中点的数量

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m个操作，操作共有三种：

C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

输入样例： 5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5 输出样例： Yes 2 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N=100010;
    static int []p=new int[N];   //存储每个节点的父节点
    static int []size=new int[N];  //查询根节点，得到整个集合数量
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String []s=br.readLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
        for (int i = 1; i <=n; i++) {
            p[i]=i;
            size[i]=1;
        }
        while (m-->0){
            String []fir=br.readLine().split(" ");
            if("C".equals(fir[0])){  //集合合并
                int pa=find(Integer.parseInt(fir[1]));
                int pb=find(Integer.parseInt(fir[2]));
                if(pa!=pb){
                    p[pa]=pb;
                    size[pb]+=size[pa];
                }
            }else if("Q1".equals(fir[0])){
                int pa=find(Integer.parseInt(fir[1]));
                int pb=find(Integer.parseInt(fir[2]));
              if(pa==pb){
                  System.out.println("Yes");
              }else System.out.println("No");
            }else {
                int pa=find(Integer.parseInt(fir[1]));
                System.out.println(size[pa]);
            }
        }
    }
    //返回每个节点的父节点
    public static int find(int x){
        if(p[x]!=x)  p[x]=find(p[x]);
        return p[x];
    }

}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-03-15，如有侵权请联系 cloudcommunity@tencent.com 删除

int