Union-Find with Path Compression
Problem Description: Find All Disjoint Sets
Idea:
1.Build roots array:
If we can build the root array as shown in the fig, we can find the root of a node. Two nodes belong to the same set if they share the same root.
(Note: The root's parent is the root itself. e.g., node 5's parent is node 1. Node 1's parent is node 0. Node 0's parent is 0. So node 0 is the root of node 5.)
2.Path compression
Because we only care about the root of a node, so rather than store its parent, it is better to store its root in the array. To achieve this, we need to implement path compression.
Key Points:
1.Use Array to represent a tree/graph.
2.Path compression
A very good tutorial:
https://www.youtube.com/watch?v=ID00PMy0-vE
Basic Algorithm:
-------------------------------------------------------------
public union_find(int[] edges, int n){
//n indicates node 0~node n-1
int[] roots = new int[n];
for(int i=0;i<n;i++) roots[i] = i;
//i indicates node i
//use "int[] roots" to construct a tree. roots[i] represents node i's parent (root if using path compression)
for(int[] edge: edges){
int root1 = find(edge[0], roots);
int root2 = find(edge[1], roots);
if(root1!=root2) merge(root1, root2, roots);
}
}
private int find(int node, int[] roots){
if(node==roots[node]) return node;
else{
roots[node] = find(roots[node],roots); //
path compression
}
return roots[node];
}
private void merge(int root1, int root2, int[] roots){
roots[root1]=root2;
}
-------------------------------------------------------------
Questions:
[323] Number of Connected Components in an Undirected Graph
[261] Graph Valid Tree
Advanced
If nodes cannot be represented as 0,1,2,3 ... (a continuous sequence), we can use a map, giving each node an id.
Questions:
[128] Longest Consecutive Sequence
Topological Sorting
Problem Description
Input: a directed graph
Output: an ordered array of nodes. (Requirement: If there is an path (0->1) in the graph, the result array should put node 0 in front of 1.)
1.Topological sorting based on DFS
1)Idea
Start from any node and do DFS. When the node has not been visited yet, its status is 0. When the node is being visited (or its descent is being visited), the node's status is 1. When the node's all descent have been visited, the node's status is 2. And it is the time to put the node into the stack.
Considering the node's descents will always be put into stack before itself, the output ordered array is the sequence of the nodes in the stack from the top to the bottom.
2) How about the loop?
When you meet a node which is being visited (status = 1), what does it mean?
YOU MEET A LOOP in the graph. Under such situations, there won't be a valid output. You might want to throw an exception now!
3) Key points
Hashmap: (int[] array) stores nodes' status.
Stack: stores the visited nodes.
DFS
4) Basic Algorithms
-----------------------------------------------------------
public int[] potologicalSort(int[][] edges, int n) throws Exception{
//n indicates node 0~node n-1
List<List<Integer>> graph = buildGraph(edges, n);
int[] visited = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=0; i<n; i++){
//If the node is in the loop (being visited)
//If the node has not been visited, do dfs
if(visited[i]==1) throw new Exception("There is a loop in the graph");
else if(visited[i]==0) dfs(i, graph, visited, stack));
}
int[] result = new int[n];
int i=0;
while(i<n) result[i++]=stack.pop();
return result;
}
private void dfs(int node, List<List<Integer>> graph, int[] visited, Stack<Integer> stack) throws Exception{
visited[node] = 1;
for(int i:graph.get(node)){
//do dfs on all children of the node
if(visited[i]==1) throw new Exception("There is a loop in the graph");
else if(visited[i]==0) dfs(i, graph, visited, stack));
}
visited[node]=2;
stack.push(node);
}
private List<List<Integer>> buildGraph(int[][] edges, int n){
//build the adjacency list of a graph
}
-----------------------------------------------------------
2.Topological sorting based on BFS
1) Idea
A node's fan-in: is the number of the node's parents (source node). e.g., in the graph, node 2's fan-in is 1, because it has a source node 0. Node 3'2 fan-in is 2 because it has 2 source nodes (node 1 and 2). Node A's fan-in = 0 means there is no node pointing to A.
The algorithm initializes the queue with all the node with fan-in=0. After we poll a node from queue, we update its children's fan-in table. Each child's fan-in -= 1. If the fan-in = 0, we add the child into the queue. So the queue maintains node collections whose fan-in = 0. The algorithm stops when there is no node in the queue.
2) How about the loop
We compare the number of nodes we visited (BFS) and the total number of nodes. If they are equal, there is no loop. Otherwise, there is a loop.
3) Key points
Queue: stores nodes with fan-in=0
HashMap: stores all nodes' fan-in number
BFS
4) Basic Algorithms
-----------------------------------------------------------
public int[] topologicalSort(int[][] edges, int n) throws Exception{
Map<Integer, List<Integer>> graph = new HashMap<>();
Queue<Integer> fanin0 = new LinkedList<>();
Map<Integer, Integer> status = new HashMap<>();
init(edges, n, graph, fanin0, status);
List<Integer> result = new ArrayList<>();
while(!queue.isEmpty()){
int len = queue.size();
//for all nodes whose fanin=0
for(int i=0;i<len;i++){
int node = queue.poll();
result.add(node);
//for each child, update its fanin number, and if it is 0, add to queue fanin0
for(int child:graph.get(node)){
int fanin = status.get(child)-1;
if(fanin==0) fanin0.add(child);
status.put(child, fanin);
}
}
}
if(result.size()!=n) throw new Exception("there is a loop!");
return toArray(result);
}
private void init(...){ ... }
private int[] toArray(...) { ... }
-----------------------------------------------------------
Compare topological sorting based on BFS and DFS
The BFS method has one advantage, compared to DFS. It can sort nodes without path order constraints, according to other ordering rules. (It is difficult to understand this, let's see the following example)
Given a directed graph (all nodes are represented by int), output an ordered array of nodes.
The requirement is:
Constraint1: If there is a path (0->1) in the graph, the result array should put node 0 in front of 1.
Constraint2: For two nodes which do not have constraint 1, the smaller node should be in front of the larger node in the output array
The output should only be: [0,1,2,4,3]
We cannot output [0,2,1,4,3]
Solution:
in the bfs method
---------------------------------------------------
while(!queue.isEmpty()){
int len = queue.size();
Collections.sort(queue);
//for all nodes whose fanin=0
for(int i=0;i<len;i++){
---------------------------------------------------
Add one line, sort the queue. So all nodes with fan-in = k are sorted.
Questions:
[332] Reconstruct Itinerary
[207] Course Schedule
[269] Alien Dictionary
Index Tree
Segment Tree
[1,2,3,4,null,5,6,null,null,null,null]
