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;
}

Share

Undirected Graph

1. BFS

2. Union Find

Directed Graph

1. Tarjan

https://www.byvoid.com/blog/scc-tarjan

Share