首页 > 试题广场 >

并查集的实现

[编程题]并查集的实现
  • 热度指数：4626 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。
  1. boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
  2. 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

输入

4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3

输出

No
Yes
Yes

说明

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

备注:

算法知识视频讲解
添加回答
Java
牛客873779487号头像 牛客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头像 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头像 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号头像 牛客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)
提交观点

问题信息

高级结构
上传者：小小
难度：
6条回答 5833浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号