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

# Find Connected Components in Directed/Undirected Graph

Undirected Graph

1. BFS

2. Union Find

Directed Graph

1. Tarjan

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

# 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;
}
q.offer(nodes.get(0));
List<Integer> component = new ArrayList<>();
Set<UndirectedGraphNode> visited = new HashSet<>();
while (!nodes.isEmpty()) {
if (q.isEmpty()) {
Collections.sort(component);
q.offer(nodes.get(0));
component = new ArrayList<>();
} else {
UndirectedGraphNode curr = q.poll();
if (!visited.contains(curr)) {
nodes.remove(curr);
for (UndirectedGraphNode neighbor : curr.neighbors) {
q.offer(neighbor);
}
}
}
}
if (!component.isEmpty()) {
}
return result;
}```

# Word Ladder I && II

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.offer(start);
int length = 1;
Set<String> visited = new HashSet<>();
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);
}
}
}
}
length++;
}
return 0;
}```

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<>();
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)) {
}
return;
}
for (String neighbor : neighborsMap.get(currStr)) {
if (distance.get(neighbor) == distance.get(currStr) + 1) {
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.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)) {
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: 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) {
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;
}
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) {