首页 > 试题广场 >

并查集的实现

[编程题]并查集的实现

热度指数：5600 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。

boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合

[要求]

如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)

输入描述:

第一行两个整数N, M。分别表示数组大小、操作次数
接下来M行，每行有一个整数opt
若opt = 1，后面有两个数x, y，表示查询(x, y)这两个数是否属于同一个集合
若opt = 2，后面有两个数x, y，表示把x, y所在的集合合并在一起

输出描述:

对于每个opt = 1的操作，若为真则输出"Yes"，否则输出"No"

示例1

输入

输出

No
Yes
Yes

说明

每次2操作后的集合为
({1}, {2}, {3}, {4})
({1}, {2, 3}, {4})
({1, 2, 3}, {4})

备注:

算法知识视频讲解

Java

醴泉

import java.io.*;

public class Main {
    // 经典并查集

    public static int MAXN = 1000001;
    public static int[] father = new int[MAXN];
    public static int[] size = new int[MAXN];
    public static int[] stack = new int[MAXN];
    public static int n;

    public static void build() {
        for (int i = 0; i <= n; ++i) {
            father[i] = i;
            size[i] = 1;
        }
    }

    // i 号节点一直往上查，找到代表节点
    public static int find(int i) {
        int size = 0; // 沿途收集了多少个节点

        // 扁平化
        while (i != father[i]) {
            stack[size++] = i; // i 收集起来
            i = father[i]; // i 往上跳
        }
        // 沿途节点收集好，i 已经跳到代表节点
        while (size > 0) {
            father[stack[--size]] = i;
        }
        return i;
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        // 小挂大优化
        if (fx != fy) {
            // fx, fy 代表大小
            if (size[fx] >= size[fy]) {
                size[fx] += size[fy];
                father[fy] = fx;
            } else {
                size[fy] += size[fx];
                father[fx] = fy;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            build();
            int m = (int) in.nval;
            for (int i = 0; i < m; ++i) {
                in.nextToken();
                int op = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                in.nextToken();
                int y = (int) in.nval;
                if (op == 1) {
                    out.println(isSameSet(x, y) ? "Yes" : "No");
                } else {
                    union(x, y);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

发表于 2024-08-10 15:13:47 回复(0)

Java

牛客873779487号

这个题目主要是没办法使用Scanner作为输入，这个作为输入时间就会超出，借用一楼的思路终于找到了原因，有试过将记录节点信息的map换成数组,不加路径扁平化，结果都影响不大，最后终于找出来是输入函数的原因，感谢一楼大佬

import java.util.*;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
UnionFindSet set = new UnionFindSet (n);
for(int i=0; i< m; i++) {
params = br.readLine().split(" ");
int opt = Integer.parseInt(params[0]),
a = Integer.parseInt(params[1]),
b = Integer.parseInt(params[2]);
if(opt==1) {
if(set.isSameSet(a,b)){
System.out.println("Yes");
}
else {
System.out.println("No");
}

}
if(opt==2) {
set.Union(a,b);
}
}
}
}

class UnionFindSet {
private int[] fatherMap; //store the element's father
private int[] rankMap; //store the set's rank
public UnionFindSet(int N) {
fatherMap = new int[N];
rankMap = new int[N];
for (int i = 0; i < N; i++) {
fatherMap[i] =i;
rankMap[i]=1;
}
}

public int FindFather(int val) {
int node=val;
while (fatherMap[node] != node) {
fatherMap[node]=fatherMap[fatherMap[node]];
node = fatherMap[node];
}

return node;
}

public boolean isSameSet(int v1, int v2) {
return FindFather(v1) == FindFather(v2);
}
public void Union(int v1, int v2) {

int h1 = FindFather(v1);
int h2 = FindFather(v2);
if (h1 == h2) {
return;
}

int rank1 = rankMap[h1];
int rank2 = rankMap[h2];
if (rank1 <= rank2) {
fatherMap[h1]=h2;
rankMap[h2]= rank1 + rank2;
rankMap[h1]=-1;
} else {
fatherMap[h2]=h1;
rankMap[h1]=rank1 + rank2;
rankMap[h2]=-1;
}
}
}

发表于 2022-07-26 21:32:00 回复(0)

Java

pein531

实现的时候使用rank来进行树高度的优化，能够提升查询速率

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < m; i++){
            params = br.readLine().split(" ");
            int opt = Integer.parseInt(params[0]), x = Integer.parseInt(params[1]), y = Integer.parseInt(params[2]);
            if(opt == 1)
                System.out.println(uf.isSameSet(x, y)? "Yes": "No");
            else
                uf.union(x, y);
        }
    }
}

class UnionFind {
    private int[] parent;         // 每个节点的父节点
    private int[] rank;           // 每个父节点的相对高度
    private int count;            // 连通分量数
    public UnionFind(int n) {
        count = n;
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    public int find(int x) {
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if(rank[rootX] > rank[rootY])          // rootY的子树更矮，将其合并到rootX的子树下
            parent[rootY] = rootX;
        else if(rank[rootX] < rank[rootY])     // rootX的子树更矮，将其合并到rootY的子树下
            parent[rootX] = rootY;
        else{
            // 否则无所谓谁合并到谁下边，不过此时需要更新树的高度
            parent[rootX] = rootY;
            rank[rootY] ++;
        }
        count--;
    }
    
    public boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    
    public int getCount() {
        return count;
    }
}

发表于 2021-11-13 20:27:37 回复(1)

Java

Jim-zht

java保存提交-：

多行输出，例如System.out.println("somesth");会导致提示运行超时。垃圾！

发表于 2021-10-28 09:55:26 回复(0)

Java

菜鸟大王

这个时间是不是卡的太死了，为啥路径压缩了也过不了

import java.util.*;

public class Main {
    static int[] p;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        p = new int[n + 10];
        for (int i = 1; i <= n; i ++) {
            p[i] = i;
        }
        while (m -- > 0) {
            int o = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            if (2 == o) {
                p[find(a)] = find(b);
            } else {
                if (find(a) == find(b)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            }
        }
    }
    static int find(int x) {
        if (x != p[x]) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

发表于 2021-01-30 21:59:40 回复(1)

Java

我是大咸鱼

import java.util.*;

public class Main {

    public static int[] team;
    public static ArrayList<Integer> ac = new ArrayList<>();
    public static ArrayList<Integer> bc = new ArrayList<>();
    public static StringBuilder sb = new StringBuilder();

    public static int findRoot(int n) {
        return team[n] == n ? n : (team[n] = findRoot(team[n]));
    }

    public static void union(int a, int b) {
        int ra = findRoot(a);
        int rb = findRoot(b);
        if (ra < rb) {
            team[rb] = ra;
        } else if (ra > rb) {
            team[ra] = rb;
        }
    }

    public static void Qmsg(int a, int b) {
        for (int i = 0; i < ac.size(); ++i) {
            union(ac.get(i), bc.get(i));
        }
        sb.append(findRoot(a) == findRoot(b) ? "Yes\n" : "No\n");
        ac.clear();
        bc.clear();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m;
        n = sc.nextInt();
        m = sc.nextInt();
        team = new int[n + 1];
        for (int i = 0; i < n; i++) {
            team[i] = i;
        }
        int a,b,opt;
        for (int i = 0; i < m; ++i) {
            opt = sc.nextInt();
            a = sc.nextInt();
            b = sc.nextInt();
            if (opt == 1) {
                Qmsg(a, b);
            } else {
                ac.add(a);
                bc.add(b);
            }
        }
        System.out.println(sb);
        // TODO code application logic here
    }
}

发表于 2020-08-06 00:40:29 回复(0)

Java

牛客755073458号

import java.util.Scanner;

public class Main{
    public static  int[] pre;
    public static  int[] count;
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int N =sc.nextInt();
        int M=sc.nextInt();
        pre = new int[N];
        initize(pre);
        int opt1;
        for(int i=0;i<M;i++){
            if( (opt1=sc.nextInt())==1) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                if (isSameSet(a,b))
                    System.out.println("Yes");
                else {
                    System.out.println("No");
                }
            }
            else{
                    union(sc.nextInt(),sc.nextInt());
                 }

        }


    }

    public static boolean isSameSet(int i, int j){
        if(find(i)!=find(j))
            return false;
        return true;


    }

    public static void union(int i, int j ){
//        pathCompress(i);
//        pathCompress(j);
        int a =find(i);
        int b=find(j);
        if(a!=b)
        {
           for(int k =0;k<pre.length;k++) {
            if (pre[k] == b)
                pre[k] = a;
           }
        }
    }

    public static void pathCompress(int x){
        //路径压缩算法
        if(x>pre.length)
            return ;
        int p=x;
        while(x!=pre[x]){
            x=pre[x];
        }
        while(x!=pre[p]){
            int temp =pre[p];
            pre[p]=x;
            p=temp;

        }
    }


    public static int find(int i){
        //递归方法。超时。
//        if(pre[i]==i)
//            return i;
//
//       return find(pre[i]);
        pathCompress(i);
        int now=i;
        int next;
        while(now!=pre[now]  ){
            now =pre[now];
       }
        return now;

    }
    public  static void initize(int[] arr){
        int i=0;
        while( i<arr.length){
            arr[i]=i;
            i++;

        }

    }

}

初学者，老是超时，求大神指教一下

发表于 2019-08-26 03:40:26 回复(0)

提交观点

问题信息

高级结构

上传者：小小

难度：

7条回答 37收藏 6513浏览

通过挑战的用户

查看代码

已注销

2023-03-12 19:07:21
大列巴_

2023-03-09 19:58:29
哈哈哈怪

2023-03-06 17:35:23
Alion666

2023-03-05 15:01:56
mirrork

2023-03-05 10:35:36

并查集的实现

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题