Union Find

[xiedaxia1hao]

并查集的作用是可以方便我们检验图的连通性。

其主要知识点看完这个视频之后，我们就基本明白了：1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find

[xiedaxia1hao]

模版题: Redundant Connection

在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

这题就是一个直接套模版的题。从 1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find 视频中我们知道，对于一个并查集来说，如果我们加入某条edge时发现这个edge的两个顶点是同一个parent的话，那说明当前的graph中有环。

所以我们直接遍历所有的edges就好，哪一条edge如果不能顺利union到我们的集合中，那就说明形成了环。

这里我们用了path compression和union by size的方式来优化我们的复杂度。

那时间复杂度如何呢？

1. 对于不加优化的union和find，每一个操作平均需要O(lgn)的时间，当我们的graph是一个linkedlist的时候，最差需要O(n)。
2. 用了union by size的优化方式后，最差情况的操作就会被优化到O(lgn)，因为union by size保证了我们的graph尽可能平均。
3. 用了path compression之后，时间复杂度就变为O(1)了，无论是average还是worst case，因为整个graph已经flattened了（深度为1）。

所以先不加优化的并查集的时间复杂度最差是O(n2)，平均是O(nlgn)。然后经过union by size和path compression之后，即使是最差情况的时间复杂度也变成了O(n)。

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        DisjointSet disjointSet = new DisjointSet(edges.length+1);
        for(int[] edge : edges) {
            if(!disjointSet.union(edge[0], edge[1])) {
                return edge;
            }
        }

        throw new IllegalArgumentException();
    }

    class DisjointSet {
        private int[] parent;
        private int[] size;

        public DisjointSet(int n) {
            if(n < 0) {
                throw new IllegalArgumentException();
            }

            // initially, the parent of each node is the each node
            parent = new int[n];
            for(int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }

            // the size of each node is 1
            size = new int[n];
            Arrays.fill(size, 1);
        }

        public int find(int x) {
            if(parent[x] == x) return x;
            return parent[x] = find(parent[x]); //Path compression by halving.
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) {
                return false;
            }

            // make root of smaller size be the children of the root with larget size.
            if(size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }

            return true;
        }
    }
}

[xiedaxia1hao]

Redundant Connection II

这道题是上面一题的follow up，从原来的无向图变成了有向图。

由题意我们可以知道，除了root是没有parent以外，其他的node都只有一个parent。

那能让该graph invalid的条件可以有以下两个：

1. root有parent了
2. 有某个node有两个parent

如果是第二种情况，我们只要对所有edge进行遍历，如果发现某个node的 indegree=2的话，那就说明某个node有两个parent了。那这里使这个graph invalid的就有两条edge是犯罪嫌疑人了。我们可以把某一条edge省略，然后看看剩下的edges能不能成环。如果剩下的edge不能成环，说明犯罪嫌疑人就是我们省略的这条edge，不然的话，犯罪嫌疑人就是另一条edge。

如果是第一种情况，那我们直接判断让该graph成环的最后一条边就行了。

代码如下：

class Solution {

    class DisjointSet {
        int[] size;
        int[] root;

        public DisjointSet(int n) {
            size = new int[n+1];
            root = new int[n+1];
            Arrays.fill(size, 1);
            for(int i = 0; i <= n; i++) {
                root[i] = i;
            }
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) {
                return false;
            }
            if(size[rootX] < size[rootY]) {
                root[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                root[rootY] = rootX;
                size[rootX] += size[rootY];
            }

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

    private int[] detectCycle(int n, int[][] edges, int[] skipEdge) {
        DisjointSet disjointSet = new DisjointSet(n);
        for(int[] e : edges) {
            if(Arrays.equals(e, skipEdge)) continue;
            if(!disjointSet.union(e[0], e[1])) {
                return e;
            }
        }
        return null;
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] indegrees = new int[n+1];
        int hasTwoIndegrees = -1;
        for(int[] e : edges) {
            indegrees[e[1]]++;
            if(indegrees[e[1]] == 2) {
                hasTwoIndegrees = e[1];
                break;
            }
        }

        if(hasTwoIndegrees != -1) {
            for(int i = n-1; i >= 0; i--) {
                if(edges[i][1] == hasTwoIndegrees) {
                    if(detectCycle(n, edges, edges[i]) == null) {
                        return edges[i];
                    }
                }
            }
        } else {
            return detectCycle(n, edges, null);
        }

        return new int[]{-1, -1};
    }
}

[xiedaxia1hao]

547. Number of Provinces

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

这题简单的来说，就是给了我们一堆edge，然后我们要把这些edge连在一起（无向图），然后看这些edge一共组成了多少个clusters。

那这题就可以直接用并查集的模版了，我们可以先遍历所有的edge，然后对每个node来说，找到他们的parent，最后所有unique的parent node的个数就是我们形成的cluster了。

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

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

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) {
                return false;
            }

            if(size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }

            return true;
        }

    }
    public int findCircleNum(int[][] isConnected) {

        int n = isConnected.length;
        DisjointSet ds = new DisjointSet(n);

        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                if(isConnected[i][j] == 1) {
                    ds.union(i, j);
                }
            }
        }

        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++) {
            set.add(ds.find(i));
        }

        return set.size();

    }
}

[xiedaxia1hao]

[737. Sentence Similarity II]()

[323. Number of Connected Components in an Undirected Graph]()

To be finished once purchased the LeetCode Premium

[xiedaxia1hao]

721. Accounts Merge

https://leetcode.com/problems/accounts-merge/discuss/140978/Easy-to-Understand-Union-Find-in-Java-95

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        int n = accounts.size();
        DisjointSet dsu = new DisjointSet(n);
        Map<String, Integer> emailToNameId = new HashMap<>();

        for(int i = 0; i < n; i++) {
            for(int j = 1; j < accounts.get(i).size(); j++) {
                String email = accounts.get(i).get(j);
                int currentNameId = i;

                if(emailToNameId.containsKey(email)) {
                    int oldMapNameId = emailToNameId.get(email);
                    dsu.union(currentNameId, oldMapNameId);
                } else {
                    emailToNameId.put(email, currentNameId);
                }
            }
        }

        Map<Integer, TreeSet> idToEmailMap = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int rootParent = dsu.find(i);
            List<String> email = accounts.get(i);
            idToEmailMap.putIfAbsent(rootParent, new TreeSet<>());
            idToEmailMap.get(rootParent).addAll(email.subList(1, email.size()));
        }

        List<List<String>> res = new ArrayList<>();
        for(int id : idToEmailMap.keySet()) {
            String name = accounts.get(id).get(0);
            List<String> emails = new ArrayList<>(idToEmailMap.get(id));
            emails.add(0, name);
            res.add(emails);
        }

        return res;
    }

    class DisjointSet {
        int[] parent;
        int[] size;

        public DisjointSet(int n) {
            parent = new int[n];
            size = new int[n];

            Arrays.fill(size, 1);
            for(int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {

            if(parent[x] != x) {
                parent[x] = find(parent[x]);
            }

            return parent[x];
        }

        public void union(int x, int y) {
            int parentX = find(x);
            int parentY = find(y);

            if(parentX == parentY) {
                return;
            }

            if(size[parentX] > size[parentY]) {
                parent[parentY] = parentX;
                size[parentX] += size[parentY];
            } else {
                parent[parentX] = parentY;
                size[parentY] += size[parentX];
            }
        }
    }
}