# 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], fathers);
int yfather = findSet(edges[i], 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;
}```
```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)) {
} else {
List<Integer> component = new ArrayList<>();
components.put(father, component);
}
}
//sort the result
List<List<Integer>> res = new ArrayList<>();
for (List<Integer> component : components.values()) {
Collections.sort(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;
}```
```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)) {
} else {
List<Integer> component = new ArrayList<>();
components.put(father, component);
}
}
//sort the result
List<List<Integer>> res = new ArrayList<>();
for (List<Integer> component : components.values()) {
Collections.sort(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;
}```