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