当前位置：网站首页>[brother hero's June training] day 26: check the collection

Union checking set , In some cases N In the application of set of elements , We usually start with each element forming a single set of elements , Then merge the set of elements belonging to the same group in a certain order , In the meantime, we need to repeatedly find out which set an element is in . In recent years, this kind of problems appear repeatedly in the international and domestic competitions of informatics . It is characterized by seemingly uncomplicated , But the amount of data is huge , If it is described by normal data structure , Often too large in space , The computer can't afford it ; Even in space , The time complexity of operation is also very high , It's impossible to run at the time specified in the competition （1～3 second ） Calculate the result required by the test question , It can only be described by concurrent query sets .

One 、 Detection loops in a two-dimensional grid

1559. Detection loops in a two-dimensional grid

class Solution {
    
    class UnionFind{
    
        int[] parent;
        int[] size;
        int n;
        int setCount;

        public UnionFind(int n){
    
            parent = new int[n];
            for(int i = 0;i<n;i++){
    
                parent[i]=i;
            }
            size = new int[n];
            Arrays.fill(size,1);
            this.n=n;
            setCount=n;
        }

        public int findset(int x){
    
            return parent[x] == x?x:(parent[x]=findset(parent[x]));
        }

        public void unite(int x,int y){
    
            // Make sure y Of  size  Small 
            if(size[x]<size[y]){
    
                int temp = x;
                x = y;
                y=temp;
            }
            parent[y]=x;
            size[x]+=size[y];
            --setCount;
        }

        public boolean findAndUnite(int x,int y){
    
            int parentX = findset(x);
            int parentY = findset(y);
            if(parentX !=parentY){
    
                unite(parentX,parentY);
                return true;
            }
            return false;
        }
    }
    public boolean containsCycle(char[][] grid) {
    
        int m = grid.length;
        int n = grid[0].length;
        UnionFind uf = new UnionFind(m*n);
        for(int i=0;i<m;++i){
    
            for(int j = 0;j<n;++j){
    
                if(i>0 && grid[i][j]==grid[i-1][j]){
    
                    if(!uf.findAndUnite(i*n+j,(i-1)*n+j)){
    
                        return true;
                    }
                }
                if(j>0 && grid[i][j]==grid[i][j-1]){
    
                    if(!uf.findAndUnite(i*n+j,i*n+j-1)){
    
                        return true;
                    }
                }
            }
        }
        return false;

    }
}

Two 、 Check if there is a valid path in the grid

1391. Check if there is a valid path in the grid

class Solution {
    
    class UnionFind{
    
        int[] f;

        public void initset(){
    
            f = new int[250010];
            for(int i = 0;i<250010;i++){
    
                f[i]=i;
            }
        }

        public int findset(int x){
    
            return f[x] == x?x:(f[x]=findset(f[x]));
        }

        public int unionset(int x,int y){
    
            int fx=findset(x);
            int fy=findset(y);
            if(fx!=fy){
    
                f[fx]=fy;
                return 1;
            }
            return 0;
        }
    }
    int[][] dir=new int[][] {
    
        {
    -1,0},{
    0,1},{
    1,0},{
    0,-1}
    };

    int[][][] data=new int [][][]{
    
        {
    {
    -1,-1,-1},{
    -1,-1,-1},{
    -1,-1,-1},{
    -1,-1,-1}},
        {
    {
    -1,-1,-1},{
    1,3,5},{
    -1,-1,-1},{
    1,4,6}},
        {
    {
    2,3,4},{
    -1,-1,-1},{
    2,5,6},{
    -1,-1,-1}},
        {
    {
    -1,-1,-1},{
    -1,-1,-1},{
    2,5,6},{
    1,4,6}},
        {
    {
    -1,-1,-1},{
    1,3,5},{
    2,5,6},{
    -1,-1,-1}},
        {
    {
    2,3,4},{
    -1,-1,-1},{
    -1,-1,-1},{
    1,4,6}},
        {
    {
    2,3,4},{
    1,3,5},{
    -1,-1,-1},{
    -1,-1,-1}}
    };
    public boolean hasValidPath(int[][] grid) {
    
        UnionFind uf=new UnionFind();
        int i,j,k;
        int m = grid.length;
        int n= grid[0].length;
        uf.initset();
        for(i=0;i<m;i++){
    
            for(j=0;j<n;++j){
    
                for(k=0;k<4;++k){
    
                    int ti=i+dir[k][0];
                    int tj=j+dir[k][1];
                    if(ti<0||tj<0||ti==m||tj==n){
    
                        continue;
                    }
                    int a = i*n+j;
                    int b = ti*n+tj;
                    int ag = grid[i][j];
                    int bg = grid[ti][tj];

                    if(data[ag][k][0]==bg|| data[ag][k][1]==bg || data[ag][k][2]==bg){
    
                        uf.unionset(a,b);
                    }
                }
            }
        }
        return uf.findset(0)==uf.findset(m*n-1);

    }
}

3、 ... and 、 Exchange elements in a string

1202. Exchange elements in a string

class Solution {
    
    int[] f;

    public void initset(int n){
    
        f = new int[n];
        for(int i = 0;i<n;i++){
    
            f[i]=i;
        }
    }

    public int findset(int x){
    
        if(x!=f[x]){
    
            f[x]=findset(f[x]);
        }
        return f[x];
    }
 

    

    
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    
        int n = s.length();
        initset(n);
        for(int j=0; j<pairs.size();j++){
    
            List<Integer> pa = pairs.get(j);
            int pre = pa.get(0);
            int aft = pa.get(1);

            int preP = findset(pre);
            int aftP = findset(aft);
            if(preP == aftP){
    
                continue;
            }
            f[preP] = aftP;
        }
        Map<Integer,PriorityQueue<Character>> map = new HashMap<>();
        for(int k = 0;k<n;k++){
    
            PriorityQueue<Character> queue = map.getOrDefault(findset(k),new PriorityQueue<>());
            queue.offer(s.charAt(k));
            map.put(f[k],queue);
        }

        StringBuilder sb=new StringBuilder();
        for(int r=0;r<n;r++){
    
            PriorityQueue<Character> tq = map.get(findset(r));
            sb.append(tq.poll());
        }
        return sb.toString();
    
    }
}