与并查集有关的问题

并查集相关的问题

解决一般的连通性问题，我们都可以用并查集来解决。

https://leetcode-cn.com/problems/friend-circles/

547、朋友圈问题

该问题是一个典型的可以用并查集解决的问题，我们只用将该二维数组中值为1的两个点连接起来就可以.

class Solution {
    private int[]parent;
    public int findCircleNum(int[][] M) {
        if(M.length==0) return 0;
        int m=M.length;
        parent=new int[m];
        //初始情况下父节点都指向自己
        for(int i=0;i<m;i++){
            parent[i]=i;
        }
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                if(M[i][j]==1) union(i,j);
            }
        }
        int res=0;
        for(int i=0;i<m;i++){
            if(parent[i]==i) res++;
        }
        return res;
    }
    private void union(int p,int q){
        int pRoot=find(p);
        int qRoot=find(q);
        parent[pRoot]=qRoot;
    }
    private int find(int p){
        while(p!=parent[p]){
            parent[p]=parent[parent[p]];
            p=parent[p];
        }
        return p;
    }
}

可以看到，我们只是简单的将并查集这种数据结构写出来，就可以轻松的解决这个问题。 如果追求性能，我们可以基于rank优化一下，这样在连接时更快. 在之前关于介绍并查集的时候有讲到过.

• 上述是一个标准的模版过程，我们只要记住这个模版即可.

https://leetcode-cn.com/problems/number-of-islands/

200、岛屿问题

• 说实话，看到这题的第一反应应该是类似于DFS，BFS
• 但是这里我们也可以采取并查集的思想来做，并且非常简单

class Solution {
    private int[]parent;
    private int[]rank;
    public int numIslands(char[][] grid) {
          if(grid.length==0||grid[0].length==0) return 0;
        int m=grid.length;
        int n=grid[0].length;
        parent=new int[m*n];
        rank=new int[m*n];
       
        for(int i=0;i<m*n;i++){
          parent[i]=i; 
            rank[i]=1;
        }
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                   if(grid[i][j]=='0') continue;
                    //坐标转换
                    int cur=j+i*n;
                    //检查四个方向
                if(i-1>=0&&grid[i-1][j]=='1') union(cur,cur-n);
                if(i+1<=m-1&&grid[i+1][j]=='1') union(cur,cur+n);
                if(j-1>=0&&grid[i][j-1]=='1') union(cur,cur-1);
                if(j+1<=n-1&&grid[i][j+1]=='1') union(cur,cur+1);
                }
            }
        int res=0;
        for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                  int cur=j+i*n;
                    if(parent[cur]==cur&&grid[i][j]=='1') res++;
                }
            } 
        return res;
      
    }
    private void union(int p,int q){
        int pRoot=find(p);
        int qRoot=find(q);
       if(qRoot==pRoot) return ;
        if(rank[pRoot]<rank[qRoot]) parent[pRoot]=qRoot;
        else if(rank[qRoot]<rank[pRoot]) parent[qRoot]=pRoot;
        else {
             parent[qRoot]=pRoot;
             rank[pRoot]++;
        }
            
    }
    private int find(int p){
        while(p!=parent[p]){
            parent[p]=parent[parent[p]];
            p=parent[p];
        }
        return p;
        
    }
}

可以看到，只要运用了并查集，这种题目将会变得非常简单，首先将大致的题意写出来，然后将并查集写出来就可以AC.

值得一提的是，本题需要向四个方向搜索，这里运用到了坐标转换，将二维转换为一维来考虑.

https://leetcode-cn.com/problems/surrounded-regions/

130、被围绕的区域

• 先说DFS做法，该题比较重要的一点就是边界上的字母不会变化，如果我们用DFS来做的话，我们可以首先在边界搜索，然后将搜索到的O变成一个奇怪的字母，最后恢复的时候，将这个奇怪的字母转化为O即可，其余的全部变成X.

  注意这个顺序，我们应该先将所有的O变成X.如果顺序颠倒，最后得到的结果应该全部是X

• 接下来讲一下关于并查集的做法，这里有一个比较有趣的想法就是我们设置一个虚拟节点，就像在做关于链表的问题时，我们总是会设置一个虚拟头节点.这里大致的思路就是，我们在边界搜索O，然后将其与虚拟节点相连，最后我们只需要查看虚拟节点是谁，并且将其恢复即可

class Solution {
    private int[]parent;
    public void solve(char[][] board) {
          if(board.length==0||board[0].length==0) return ;
        int m=board.length;
        int n=board[0].length;
        parent=new int[m*n+1];
        for (int i=0;i<=m*n;i++){
            parent[i]=i;
        }
        //虚拟节点
        int dummy=m*n;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //我们只需要考虑'O'即可
                if(board[i][j]=='X') continue;
                int cur=i*n+j;
                //边界情况,与虚拟节点连接
                if(i==0||j==0||i==m-1||j==n-1){
                    union(cur,dummy);
                    continue;
                }
             if(i-1>=0&&board[i-1][j]=='O') union(cur,cur-n);
             if(i+1<=m-1&&board[i+1][j]=='O') union(cur,cur+n);
             if(j-1>=0&&board[i][j-1]=='O') union(cur,cur-1);
             if(j+1<=n-1&&board[i][j+1]=='O') union(cur,cur+1);
                
            }
        }
        //找出虚拟节点
        int dummy_pos=parent[dummy];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='X')continue;
                int cur=i*n+j;
                //如果该节点不与虚拟节点相连
           if(find(cur)!=dummy_pos)  board[i][j]='X';
                
            }
        }
    }
    private void union(int p,int q){
        int pRoot=find(p);
        int qRoot=find(q);
         if(qRoot==pRoot) return ;
        parent[pRoot]=qRoot;
    }
    private int find(int p){
        while(p!=parent[p]){
            parent[p]=parent[parent[p]];
            p=parent[p];
        }
        return p;
    }
}

通过上面三道题目，我相信对并查集解题已经有了一定的想法了

赏

谢谢你请我喝奶茶

微信