Union-Find 并查集

Union-Find is an algorithm which is widely used to solve finding disjoint components.

void init(int[] nums) {
    int[] fathers = new int[nums.length];
    //initially, father is itself
    for (int i = 0; i < nums; i++) {
        fathers[i] = i;
    }
}

//find the father for both nodes
//if they are in different groups, union them by setting fathers[xFather] = yFather;
void union(int x, int y, int[] fathers) {
    int xFather = findAndSet(x, fathers);
    int yFather = findAndSet(y, fathers);
    fathers[xFather] = yFather;
}

//recursively find its parent until reach the top which its parent is itself
//to improve the performance, we compress the path by setting the top father
//so that next time we call find, it is O(1) time complexity
int findAndSet(int x, int[] fathers) {
    int parent = fathers[x];
    while (parent != fathers[parent]) {
        parent = fathers[parent];
    }
    return parent;
}

Related Questions:

1. Graph Valid Tree Medium

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

    Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

    //union-find algorithm
    //findSet is a faster version of find method which finds the top father of a node
    //and then set the father to
    //which basically compress the path.
    //another improvement could be: only
    public boolean validTree(int n, int[][] edges) {
        int[] fathers = new int[n];
        for (int i = 0; i < n; i++) {
            fathers[i] = i;
        }
        for (int i = 0; i < edges.length; i++) {
            //union
            int xfather = findSet(edges[i][0], fathers);
            int yfather = findSet(edges[i][1], fathers);
            //since there is no duplicate edge(important! otherwise this algorithm is wrong)
            //so if xfather == yfather means they are in
            if (xfather == yfather) {
                return false;
            }
            fathers[xfather] = yfather;
        }
        //there should only be one node(root) pointing to itself
        int count = 0;
        for (int i = 0; i < fathers.length; i++) {
            if (fathers[i] == i) {
                count++;
            }
        }
        return count == 1;
    }
    
    public int findSet(int x, int[] fathers) {
        int parent = fathers[x];
        while (parent != fathers[parent]) {
            parent = fathers[parent];
        }
        fathers[x] = parent;
        return parent;
    }

    2. Find the Connected Component in the Undirected Graph

    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        //init unions
        Map<Integer, Integer> fathers = new HashMap<>();
        for (UndirectedGraphNode node : nodes) {
            int label = node.label;
            if (!fathers.containsKey(label)) {
                fathers.put(label, label);
            }
            for (UndirectedGraphNode neighbor : node.neighbors) {
                union(label, neighbor.label, fathers);
            }
        }
        //put it into a new map which key is the father of the component
        //value is a list of node within the component
        Map<Integer, List<Integer>> components = new HashMap<>();
        for (Integer label : fathers.keySet()) {
            int father = findAndSet(label, fathers);
            if (components.containsKey(father)) {
                components.get(father).add(label);
            } else {
                List<Integer> component = new ArrayList<>();
                component.add(label);
                components.put(father, component);
            }
        }
        //sort the result
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> component : components.values()) {
            Collections.sort(component);
            res.add(component);
        }
        return res;
    }
    
    public void union(int x, int y, Map<Integer, Integer> fathers) {
        int xFather = findAndSet(x, fathers);
        int yFather = findAndSet(y, fathers);
        if (xFather != yFather) {
            fathers.put(xFather, yFather);
        }
    }
    
    public int findAndSet(int label, Map<Integer, Integer> fathers) {
        if (!fathers.containsKey(label)) {
            fathers.put(label, label);
            return label;
        }
        int parent = fathers.get(label);
        while (parent != fathers.get(parent)) {
            parent = fathers.get(parent);
        }
        fathers.put(label, parent);
        return parent;
    }

    3. Find the Weak Connected Component in the Directed Graph

    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        //init unions
        Map<Integer, Integer> fathers = new HashMap<>();
        for (DirectedGraphNode node : nodes) {
            int label = node.label;
            if (!fathers.containsKey(label)) {
                fathers.put(label, label);
            }
            for (DirectedGraphNode neighbor : node.neighbors) {
                union(label, neighbor.label, fathers);
            }
        }
        //put it into a new map which key is the father of the component
        //value is a list of node within the component
        Map<Integer, List<Integer>> components = new HashMap<>();
        for (Integer label : fathers.keySet()) {
            int father = findAndSet(label, fathers);
            if (components.containsKey(father)) {
                components.get(father).add(label);
            } else {
                List<Integer> component = new ArrayList<>();
                component.add(label);
                components.put(father, component);
            }
        }
        //sort the result
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> component : components.values()) {
            Collections.sort(component);
            res.add(component);
        }
    
        return res;
    }
    
    public void union(int x, int y, Map<Integer, Integer> fathers) {
        int xFather = findAndSet(x, fathers);
        int yFather = findAndSet(y, fathers);
        if (xFather != yFather) {
            fathers.put(xFather, yFather);
        }
    }
    
    public int findAndSet(int label, Map<Integer, Integer> fathers) {
        if (!fathers.containsKey(label)) {
            fathers.put(label, label);
            return label;
        }
        int parent = fathers.get(label);
        while (parent != fathers.get(parent)) {
            parent = fathers.get(parent);
        }
        fathers.put(label, parent);
        return parent;
    }
    FacebookTwitterGoogle+Share

    Find the Connected Component in the Undirected Graph

    Find the Connected Component in the Undirected Graph

    Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

    Example

    Given graph:

    A------B  C
     \     |  | 
      \    |  |
       \   |  |
        \  |  |
          D   E

    Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

    Solution: BFS

    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        List<List<Integer>> result = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) {
            return result;
        }
        Queue<UndirectedGraphNode> q = new LinkedList<>();
        q.offer(nodes.get(0));
        List<Integer> component = new ArrayList<>();
        Set<UndirectedGraphNode> visited = new HashSet<>();
        while (!nodes.isEmpty()) {
            if (q.isEmpty()) {
                Collections.sort(component);
                result.add(new ArrayList<>(component));
                q.offer(nodes.get(0));
                component = new ArrayList<>();
            } else {
                UndirectedGraphNode curr = q.poll();
                if (!visited.contains(curr)) {
                    visited.add(curr);
                    nodes.remove(curr);
                    component.add(curr.label);
                    for (UndirectedGraphNode neighbor : curr.neighbors) {
                        q.offer(neighbor);
                    }
                }
            }
        }
        if (!component.isEmpty()) {
            result.add(component);
        }
        return result;
    }

    Word Ladder I && II

    Word Ladder I  — 只需要找一条最短路

    Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

    1. Only one letter can be changed at a time
    2. Each intermediate word must exist in the dictionary

    Example

    Given:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

    As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
    return its length 5.

    Note

    • Return 0 if there is no such transformation sequence.
    • All words have the same length.
    • All words contain only lowercase alphabetic characters.

    Solution: BFS – BFS模板 O(n*L) n: size of dict, L: the max length of the words

    visited set记录已经访问过的路 一旦找到一条就退出

    注意字符串的处理

    public int ladderLength(String start, String end, Set<String> dict) {
        if (dict == null || dict.size() == 0) {
            return 0;
        }
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        int length = 1;
        Set<String> visited = new HashSet<>();
        visited.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                    for (int j = 0; j < start.length(); j++) {
                        if (newChar == curr.charAt(j)) {
                            continue;
                        }
                        String nextStep = curr.substring(0, j) + newChar + curr.substring(j + 1);
                        if (nextStep.equals(end)) {
                            return length + 1;
                        }
                        if (dict.contains(nextStep) && !visited.contains(nextStep)) {
                            queue.offer(nextStep);
                            visited.add(nextStep);
                        }
                    }
                }
            }
            length++;
        }
        return 0;
    }

    Word Ladder II –找出所有最短路

    Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

    1. Only one letter can be changed at a time
    2. Each intermediate word must exist in the dictionary
    Example

    Given:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

    Return

      [
        ["hit","hot","dot","dog","cog"],
        ["hit","hot","lot","log","cog"]
      ]
    
    Note

    • All words have the same length.
    • All words contain only lowercase alphabetic characters.

    Solution: BFS+DFS

    1. 先用BFS找出最短路径的长度,同时把相邻节点和每个点到起点的distance保存下来

    2. 用DFS找出所有最短路径,distance超过最短路径的长度的就不用考虑了,所谓pruning.

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> result = new ArrayList<>();
        if (dict == null || dict.size() == 0) {
            return result;
        }
        List<String> curr = new ArrayList<>();
        curr.add(start);
        Map<String, Integer> distance = new HashMap<>();
        Map<String, List<String>> neighborsMap = new HashMap<>();
        int minTrans = bfs(start, end, dict, distance, neighborsMap);
        findLaddersHelper(curr, end, minTrans, distance, neighborsMap, result);
        return result;
    }
    
    public void findLaddersHelper(List<String> curr, String end, int maxStep, Map<String, Integer> distance,
                                  Map<String, List<String>> neighborsMap, List<List<String>> result) {
        String currStr = curr.get(curr.size() - 1);
        if (maxStep == 0) {
            if (currStr.equals(end)) {
                result.add(new ArrayList<>(curr));
            }
            return;
        }
        for (String neighbor : neighborsMap.get(currStr)) {
            if (distance.get(neighbor) == distance.get(currStr) + 1) {
                curr.add(neighbor);
                findLaddersHelper(curr, end, maxStep - 1, distance, neighborsMap, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
    
    //first use BFS to find the shortest transformation
    public int bfs(String start, String end, Set<String> dict,
                   Map<String, Integer> distance, Map<String, List<String>> neighborsMap) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        distance.put(start, 0);
        int minTrans = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            String str = queue.poll();
            List<String> neighbors = new ArrayList<>();
            for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                for (int index = 0; index < start.length(); index++) {
                    if (newChar == str.charAt(index)) {
                        continue;
                    }
                    String newStr = str.substring(0, index) + newChar + str.substring(index + 1);
                    if (newStr.equals(end) && minTrans == -1) {
                        minTrans = distance.get(str) + 1;
                    }
                    if (dict.contains(newStr)) {
                        neighbors.add(newStr);
                        if (!distance.containsKey(newStr)) {
                            distance.put(newStr, distance.get(str) + 1);
                            queue.offer(newStr);
                        }
                    }
                }
            }
            neighborsMap.put(str, neighbors);
        }
        return minTrans;
    }

    Topological Sorting

    Topological Sorting

    Given an directed graph, a topological order of the graph nodes is defined as follow:

    • For each directed edge A -> B in graph, A must before B in the order list.
    • The first node in the order can be any node in the graph with no nodes direct to it.

    Find any topological order for the given graph.

    Example

    For graph as follow:

    picture

    The topological order can be:

    <code>[0, 1, 2, 3, 4, 5]
    [0, 2, 3, 1, 5, 4]
    ...
    </code>
    Note

    You can assume that there is at least one topological order in the graph.

    Challenge

    Can you do it in both BFS and DFS?

    Solution 1. BFS

    1. first create a map which contains all the nodes and its indegrees

    2. only add node with 0 indegree to the list and once the node is select, remove 1 indegree from all its neighbors

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        //BFS
        ArrayList<DirectedGraphNode> result = new ArrayList<>();
        if (graph == null || graph.size() <= 1) {
            return graph;
        }
        HashMap<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
        for (DirectedGraphNode node : graph) {
            if (!inDegreeMap.containsKey(node)) {
                inDegreeMap.put(node, 0);
            }
            for (DirectedGraphNode neighbor : node.neighbors) {
                if (inDegreeMap.containsKey(neighbor)) {
                    inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) + 1);
                } else {
                    inDegreeMap.put(neighbor, 1);
                }
            }
        }
        while (!inDegreeMap.isEmpty()) {
            for (DirectedGraphNode node : inDegreeMap.keySet()) {
                if (inDegreeMap.get(node) == 0) {
                    result.add(node);
                    inDegreeMap.remove(node);
                    for (DirectedGraphNode neighbor : node.neighbors) {
                        inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
                    }
                    break;
                }
            }
        }
        return result;
    }

    Clone Graph

    Clone Graph

    Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
    OJ’s undirected graph serialization:

    Nodes are labeled uniquely.

    We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

    As an example, consider the serialized graph {0,1,2#1,2#2,2}.

    The graph has a total of three nodes, and therefore contains three parts as separated by #.

    1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
    2. Second node is labeled as 1. Connect node 1 to node 2.
    3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

    Visually, the graph looks like the following:

           1
          / \
         /   \
        0 --- 2
             / \
             \_/
    

    Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射
    O(n) time complexity, O(n) space

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        queue.offer(node);
        UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label);
        map.put(node, copyRoot);
        while (!queue.isEmpty()) {
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                UndirectedGraphNode curr = queue.poll();
                for (UndirectedGraphNode neighbor : curr.neighbors) {
                    if (!map.containsKey(neighbor)) {
                        queue.offer(neighbor);
                        UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label);
                        map.put(neighbor, currCopy);
                    }
                }
            }
        }
        for (UndirectedGraphNode originalNode : map.keySet()) {
            for (UndirectedGraphNode neighbor : originalNode.neighbors) {
                map.get(originalNode).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }