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