并查集(UnionFind) 系列

547. Number of Provinces

Medium

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

解法1: 并查集

class Solution {
    public int findCircleNum(int[][] isConnected) {
        //1.for loop len elements do unionfind
        UnionFind uf = new UnionFind(isConnected.length);
        for(int i=0;i){
            for(int j=0;j){
                if(i!=j && isConnected[i][j]==1) {
                    uf.union(i,j);
                }
            }
        }
        //2.count the parent[i]=i
        int count = 0;
        for(int i=0;i) 
            if(uf.parent[i]==i) count++;
        return count;
    }
    //UnionFind implementation
    class UnionFind{
        int[] parent;
        int[] rank;
        UnionFind(int n){
            parent = new int[n];
            rank = new int[n];
            for(int i=0;ii;
        }
        public int findParent(int x){
            if(x==parent[x]) return x;
            parent[x] = findParent(parent[x]);
            return parent[x];
        }
        public void union( int x,int y ){
            int px = findParent(x);
            int py = findParent(y);
            if(px==py) return;
            if(rank[px]>rank[py])    parent[py]=px;
            else if(rank[px]py;
            else{
                parent[px]=py;
                rank[py]++;
            }
        }
    }
}

 解法二： dfs

class Solution {
    public int findCircleNum(int[][] isConnected) {
        //defind visited
        int len = isConnected.length;
        boolean[] visited = new boolean[len];
        //for loop 0 ~ len-1  recursively find its connections
        int count = 0;
        for(int i=0;i){
            if(visited[i]) continue;
            count++;
            dfs(isConnected,i,visited);
        }
        return count;
    }
    private void dfs(int[][] isConnected,int i,boolean[] visited){
        int len = isConnected.length;
        visited[i]=true;
        for(int j=0;j){
            if(isConnected[i][j]==1 && !visited[j] ) dfs(isConnected,j,visited);
        }
    }
}

434 · Number of Islands II Algorithms Medium Description

Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.You need to return an array of size K.

0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Example

Example 1:

Input: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
Output: [1,1,2,2]
Explanation:
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011

Example 2:

Input: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]
Output: [1,1,2,2]

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

public class Solution {
    /**
     * @param n: An integer
     * @param m: An integer
     * @param operators: an array of point
     * @return: an integer array
     */
    public List numIslands2(int m, int n, Point[] operators) {
        List result = new ArrayList();
        UnionFind uf = new UnionFind(m*n);
        int count=0;
        int[][] directions = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        boolean[][] visited = new boolean[m][n];
        if(operators==null) return result;
        for(Point p:operators){
            //重复元素直接跳过
            if(visited[p.x][p.y]) {//坑点1:重复元素记得跳过
                result.add(count);
                continue;
            }
            count++;
            visited[p.x][p.y]=true;
            for(int[] dir:directions){
                int nx = p.x+dir[0];
                int ny = p.y+dir[1];
                if( nx>=0 && ny>=0 && nxn ){
                    if(visited[nx][ny] && (uf.find(nx*n+ny)!=uf.find(p.x*n+p.y))){//坑点2:这里的列数是n，不是m， 因此是p.x*n+p.y   ，另外当且仅当相邻点已经被访问过并且还没有连通的情况下才进行连通并count--
                        count--;
                        uf.union(p.x*n+p.y,nx*n+ny);
                    }
                }
            }
            result.add(count);
        }
        return result;
    }
    class UnionFind{
        int[] parent;
        UnionFind(int n){
            parent = new int[n];
            for(int i=0;ii;
        }
        int find(int x){
            if(x==parent[x]) return x;
            parent[x] = find(parent[x]);
            return parent[x];
        }
        void union(int x,int y){
            int px = find(x);
            int py = find(y);
            if(px==py) return;
            parent[px]=py;
        }
    }
}

 128. Longest Consecutive Sequence

Medium

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

解法一：使用并查集记录元素下标，然后对每个元素进行两侧数字连接

class Solution {
    public int longestConsecutive(int[] nums) {
        Map map = new HashMap();
        UnionFind uf = new UnionFind(nums.length);
        for(int i=0;i){
            if(map.containsKey(nums[i])) continue;
            map.put(nums[i],i);
            if(map.get(nums[i]+1)!=null) uf.union(i,map.get(nums[i]+1));
            if(map.get(nums[i]-1)!=null) uf.union(i,map.get(nums[i]-1));
        }
        int max = 0;
        for(int i=0;i Math.max(max,uf.size[i]);
        return max;
    }
    class UnionFind{
        int[] parent;
        int[] size;
        UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            for(int i=0;i) {
                parent[i]=i;
                size[i]=1;
            }
        }
        int findParent(int i){
            if(parent[i]==i) return i;
            parent[i] = findParent(parent[i]);
            return parent[i];
        }
        void union(int x,int y){
            int px = findParent(x);
            int py = findParent(y);
            if(px==py) return ;
            parent[px]=py;
            size[py]+=size[px];
        }
    }
}

 解法二：使用hashset，保存所有元素，迭代数组元素从set移除两侧相邻元素直至找不到相邻

class Solution {
    public int longestConsecutive(int[] nums) {
        Set set = new HashSet();
        for(int num:nums) set.add(num);
        int max = 0;
        for(int num:nums){
            if(!set.remove(num)) continue;
            //以当前元素开始向两侧查找相邻元素
            int left = num-1;
            int right = num+1;
            while(set.remove(left)) left--;
            while(set.remove(right)) right++;
            //记录此次遍历的最大范围
            max = Math.max(right-left-1,max);
        }
        return max;
    }
}

 684. Redundant Connection

Medium

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4] 

Constraints:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind(edges.length);
        //逐条遍历edge，如果两个端点已经连接，那么这条边即为造成环的那条边；否则把他们union起来
        for(int[] edge:edges){
            if(uf.findParent(edge[0]-1)==uf.findParent(edge[1]-1)) return edge;//坑点，注意顶点时从1开始的，但是unionfind中是从0开始的
            uf.union(edge[0]-1,edge[1]-1);
        }
        return null;
    }
    class UnionFind{
        int[] parent;
        UnionFind(int n){
            parent = new int[n];
            for(int i=0;ii;
        }
        int findParent( int x ){
            if(parent[x]==x) return x;
            parent[x] = findParent(parent[x]);
            return parent[x];
        }
        void union(int x,int y){
            int px = findParent(x);
            int py = findParent(y);
            if(px==py) return;
            parent[px]=py;
        }
    }
}

399. Evaluate Division Medium

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000] 

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj consist of lower case English letters and digits.

class Solution {
    public double[] calcEquation(List> equations, double[] values, List> queries) {
        UnionFind uf = new UnionFind();
        for(int i=0;i){
            String divid1 = equations.get(i).get(0);
            String divid2 = equations.get(i).get(1);
            uf.union(divid1,divid2,values[i]);
            uf.print();
        }
        double[] result = new double[queries.size()];
        for(int i=0;i){
            String divid1 = queries.get(i).get(0);
            String divid2 = queries.get(i).get(1);
            Pair parent1 = uf.findParent(divid1);
            Pair parent2 = uf.findParent(divid2);
            if(parent1==null || parent2==null || !parent1.parent.equals(parent2.parent)) //记得不仅仅是某个元素没出现时为-1，如果两个元素没有连通的时候也是-1
                result[i]=-1; 
            else 
                result[i]= parent1.weight/parent2.weight;
        }
        return result;
    }
    class Pair{
        String parent;
        double weight;
        Pair(String parent,double weight){
            this.parent = parent;
            this.weight = weight;
        }
    }
    class UnionFind{
        Map map;
        UnionFind(){
            map = new HashMap();
        }
        Pair findParent(String str){
            Pair pair = map.get(str);
            if(pair==null) return null;
            if(pair.parent.equals(str)) return pair;
            Pair gpair = findParent(pair.parent);
            pair.parent = gpair.parent;
            pair.weight = gpair.weight*pair.weight;
            return pair;
        }
        void union(String x,String y,double weight){
            Pair parentX = findParent(x);
            Pair parentY = findParent(y);
            if(parentX==null && parentY==null){//如果X,Y均没有出现过，直接添加并且连通
                parentX= new Pair(y,weight);
                parentY= new Pair(y,1.0);
                map.put(x,parentX);
                map.put(y,parentY);
            }
            else if(parentX==null){//如果X没出现过，将它挂到Y上
                parentX= new Pair(y,weight);
                map.put(x,parentX);
            }
            else if(parentY==null){//如果Y没出现过，将它挂到X上
                parentY = new Pair(x,1/weight);
                map.put(y,parentY);
            }
            else{//如果两个都出现过，那么当前我们拿到的时候他们的parent，此时要把他们的parent挂起来
                map.put(parentX.parent, 
                  new Pair(parentY.parent, weight / parentX.weight * parentY.weight));
            }
        }
    }
}