并查集

package org.example.oj;

import java.util.*;

public class Test24{
    static int N=100010;
    static int[] father=new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String[] str=sc.nextLine().split(" ");
        int n=Integer.parseInt(str[0]);
        int m=Integer.parseInt(str[1]);
        //初始化
        init(n);
        for(int i=0;i<m;i++){
            String s="";
            if(sc.hasNext()){
                s=sc.nextLine();
            }
            String[] ss=s.split(" ");
            if(ss[0].equals("M")){
                int a=Integer.parseInt(ss[1]);
                int b=Integer.parseInt(ss[2]);
                father[find(a)]=find(b);
            }else if(ss[0].equals("Q")){
                int a=Integer.parseInt(ss[1]);
                int b=Integer.parseInt(ss[2]);
                if(find(a)==find(b)){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }

    public static int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }

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

}

• 判断两个元素是否在一个集合
• 将两个集合合并

通过size[]维护每一个集合的节点数 所有的节点所在集合的节点数只需要通过根节点进行维护即可

import java.util.*;

public class Main{
    static int N=100010;
    static int[] father=new int[N];
    static int[] cnt=new int[N];//每一个节点所属集合节点总数
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String[] str=sc.nextLine().split(" ");
        int n=Integer.parseInt(str[0]);int m=Integer.parseInt(str[1]);
        init(n);
        for(int i=0;i<m;i++){
            String s="";
            if(sc.hasNext()){
                s=sc.nextLine();
            }
            String[] ss=s.split(" ");
            if(ss[0].equals("C")){
                int a=Integer.parseInt(ss[1]);
                int b=Integer.parseInt(ss[2]);
                if(find(a)==find(b)){
                    continue;
                }
                cnt[find(b)]=cnt[find(a)]+cnt[find(b)];
                father[find(a)]=find(b);
            }else if(ss[0].equals("Q1")){
                int a=Integer.parseInt(ss[1]);
                int b=Integer.parseInt(ss[2]);
                System.out.println(find(a)==find(b)? "Yes":"No");
            }else if(ss[0].equals("Q2")){
                int a=Integer.parseInt(ss[1]);
                System.out.println(cnt[find(a)]);
            }
        }
    }
    public static int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }
    public static void init(int n){
        for(int i=1;i<=n;i++){
            cnt[i]=1;
            father[i]=i;
        }
    }
}

如果可能合并的两个节点属于同一个集合 需要continue

账户合并 并查集应用

账户合并
将所有的邮箱进行唯一性编号，编号之后将对应的编号id通过并查集合并
然后将合并之后对应的相同father[]的所有的邮箱进行合并
通过建立邮箱到name的映射，将最后的结果进行整理输出

class Solution {
   int[] father;
    public List<List<String>> accountsMerge(List<List<String>> accounts){
        //将所有的账号邮箱唯一编号
        Map<String,Integer> emailToIndex=new HashMap<String,Integer>();
        Map<String,String> emailToName=new HashMap<>();
        int emailIndex=0;
        for (List<String> account : accounts) {
            String name=account.get(0);
            int size=account.size();
            for(int i=1;i<size;i++){
                String email=account.get(i);
                if(!emailToIndex.containsKey(email)){
                    emailToIndex.put(email,emailIndex++);
                    emailToName.put(email,name);
                }
            }
        }
        //初始化并查集
        father=new int[emailIndex];
        init();
        for (List<String> account : accounts) {
            String name=account.get(0);
            int size=account.size();
            //第一个email
            int firstemail=emailToIndex.get(account.get(1));
            for(int i=2;i<size;i++){
                int nextemail=emailToIndex.get(account.get(i));
                father[find(firstemail)]=find(nextemail);
            }
        }
        //将所有的相同id邮箱放在同一个id下
        Map<Integer,List<String>> indexToEmail=new HashMap<>();
        Set<Map.Entry<String, Integer>> entries = emailToIndex.entrySet();
        for(Map.Entry<String,Integer> entry:entries){
            String email=entry.getKey();
            Integer id=find(entry.getValue());
            List<String> acc=indexToEmail.getOrDefault(id,new ArrayList<String>());
            acc.add(email);
            indexToEmail.put(id,acc);
        }

        //将结果进行封装
        List<List<String>> res=new ArrayList<>();
        Set<Integer> keys = indexToEmail.keySet();

        for (Integer key : keys) {
            List<String> re=indexToEmail.get(key);
            Collections.sort(re);
            String name=emailToName.get(re.get(0));
            re.add(0,name);
            res.add(re);
        }
        return res;
    }

    public void init(){
        for(int i=0;i<father.length;i++){
            father[i]=i;
        }
    }

    public int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }
}

矩阵转换之后的秩

矩阵转换之后的秩
通过并查集维护行列相同的点的秩相同，通过并查集只需要更新leader节点的秩

class Solution {
    int[] father;
    public int[][] matrixRankTransform(int[][] matrix){
        int n=matrix.length;int m=matrix[0].length;
        Integer[] indexs=new Integer[m*n];
        int[] vals=new int[m*n];
        //所有相同元素秩通过并查集维护

        father=new int[m*n];

        for(int i=0;i<m*n;i++){
            indexs[i]=i;
            father[i]=i;
        }
        //将对应的排序
        Arrays.sort(indexs,(a,b)->matrix[a/m][a%m]-matrix[b/m][b%m]);

        //对于最大值进行记录
        int[] row=new int[n];
        int[] col=new int[m];
        //初始化为-1
        Arrays.fill(row,-1);Arrays.fill(col,-1);

        //对每一个最小元素进行排序
        int pos=0;
        while (pos < m * n) {
            int val=1;
            int index=indexs[pos];
            int i=index/m;
            int j=index%m;
            if(row[i]!=-1){
                int k=row[i];
                int position=i*m+k;
                int tmp_rank=vals[find(position)];
                if(matrix[i][j]==matrix[i][k]){
                    val=tmp_rank;
                    //合并并查集
                    father[find(index)]=find(position);
                }else{
                    val=tmp_rank+1;
                }
            }

            if(col[j]!=-1){
                int k=col[j];
                int position=k*m+j;
                int tmp_rank=vals[find(position)];
                if(matrix[i][j]==matrix[k][j]){
                    val=Math.max(tmp_rank,val);
                    father[find(index)]=find(position);
                }else{
                    val=Math.max(val,tmp_rank+1);
                }
            }
            //记录最大位置
            row[i]=j;
            col[j]=i;//更新之后当前位置一定是最大rank位置
            vals[find(index)]=val;
            pos++;
        }

        int[][] res=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                res[i][j]=vals[find(i*m+j)];
            }
        }

        return res;
    }

    public int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }
}

尽量减少恶意软件传播

尽量减少恶意软件传播

class Solution {
       int[] father;
    int[] size;
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n=graph.length;
        init(n);

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(graph[i][j]==1){
                    size[find(j)]+=size[find(i)];//先修改连通块大小，再将连通块合并
                    father[find(i)]=find(j);
                }
            }
        }
        int[] cnt=new int[n];
        //联通块大小
        for (int node : initial) {
            cnt[find(node)]++;
        }
        int re=-1;int count=-1;
        for (int node : initial) {
            int root=find(node);
            if(cnt[root]==1){
                int rootSize=size[find(root)];
                if(rootSize>count){
                    count=rootSize;
                    re=node;
                }else if(rootSize==count&&node<re){
                     count=rootSize;
                    re=node;
                }
            }
        }
        if(re==-1){
            //没有联通块被感染节点为1
            //取最小的被感染节点
            re=Integer.MAX_VALUE;
            for (int node : initial) {
                re=Math.min(re,node);
            }
        }
        return re;
    }
    public void init(int n){
        size=new int[n];
        father=new int[n];
        for(int i=0;i<n;i++){
            father[i]=i;
            size[i]=1;
        }
    }

    public int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }

}

减少恶意软件的传播

减少恶意软件传播

class Solution {
    int[] father;
    int[] size;
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n=graph.length;
        init(n);
        //所有有毒节点
        Set<Integer> set=new HashSet<Integer>();
        for (int node : initial) {
            set.add(node);
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!set.contains(i)&&!set.contains(j)&&graph[i][j]==1&&find(i)!=find(j)){
                    size[find(i)]+=size[find(j)];
                    father[find(j)]=find(i);
                }
            }
        }

        //统计联通块数量
        Set<Integer> comp=new HashSet<>();
        for(int i=0;i<n;i++){
            if (!set.contains(i)) {
                comp.add(find(i));
            }
        }

        //每一个连通块有毒节点
        Set<Integer>[] cnt=new Set[n];
        //初始化
        for(int i=0;i<n;i++){
            cnt[i]=new HashSet<Integer>();
        }

        for (int node : initial) {
            for(int i=0;i<n;i++){
                if(!set.contains(i)&&graph[i][node]==1){
                   cnt[find(i)].add(node);
                }
            }
        }

        int[] sum=new int[n];

        for (Integer node : comp) {
            if(cnt[node].size()==1){
                for (Integer i : cnt[node]) {
                    sum[i]+=size[node];
                }
            }
        }

        int res=initial[0];
        for(int i=0;i<initial.length;i++){
            if(sum[initial[i]]>sum[res]||(sum[initial[i]]==sum[res]&&initial[i]<res)){
                res=initial[i];
            }
        }
        return res;
    }

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

    public int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }
}

并查集逆向操作，针对正向操作删除一条边维护连通块，通过逆向操作维护添加一条边，并查集联通情况

打砖块

打砖块
并查集维护添加一条边，连通块的联通情况，通过将操作逆过来，可以维护删除一条边，并查集的联通情况

class Solution {
    int[] father;
    int[] size;
    int m;
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int n=grid.length;m=grid[0].length;
        init(n*m+1);
        boolean[] st=new boolean[hits.length];
        for(int i=0;i<hits.length;i++){
            int x=hits[i][0];int y=hits[i][1];
            if(grid[x][y]==1){
                //需要进行操作
                st[i]=true;
                //将对应的位置置为0
                grid[x][y]=0;
            }else{
                st[i]=false;
            }
        }
        int S=m*n;
        //将所有的点通过并查集进行维护
        int[] dx={0,1,0,-1};
        int[] dy={1,0,-1,0};
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    //如果是第一行
                    int a=get(i,j);
                    if(i==0){
                        if(find(S)!=find(a)){
                            //合并到顶部
                            size[find(S)]+=size[find(a)];
                            father[find(a)]=find(S);
                        }
                    }
                    //对于周围的点
                    //并且没有进行越界的点
                    for(int k=0;k<4;k++){
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1){
                            //进行合并
                            int b=get(x,y);
                            if(find(a)!=find(b)){
                                size[find(b)]+=size[find(a)];
                                father[find(a)]=find(b);
                            }
                        }
                    }
                }
            }
        }
        //对于逆序操作
        int last=size[find(S)];
        int[] res=new int[hits.length];
        for(int i=hits.length-1;i>=0;i--){
            if(st[i]){
                //可以进行操作
                int x=hits[i][0];int y=hits[i][1];
                grid[x][y]=1;
                int a=get(x,y);
                //如果添加在第一行
                if(x==0){
                    if(find(a)!=find(S)){
                        size[find(S)]+=size[find(a)];
                        father[find(a)]=find(S);
                    }
                }
                for(int k=0;k<4;k++){
                    int next_x=x+dx[k];int next_y=y+dy[k];
                    int b=get(next_x,next_y);
                    if(next_x>=0&&next_x<n&&next_y>=0&&next_y<m&&grid[next_x][next_y]==1){
                        if(find(a)!=find(b)){
                            size[find(b)]+=size[find(a)];
                            father[find(a)]=find(b);   
                        }
                    }
                }
            }
            //计算对应的位置
            res[i]=Math.max(0,size[find(S)]-last-1);
            //对于不需要进行操作，比较之后取0
            last=size[find(S)];
        }
        return res;
    }

    public int get(int i,int j){
        return i*m+j;
    }

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

    public int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }
}