Union find is helpful to build relationship among different sets

Key operations: union, find, etc.

**Basic Abstractions**

Name | Summary |
---|---|

Entities | Set of objects |

Union command | Connect two objects or two groups |

Find query | Is there a path connecting one object to another? |

Disjoint sets of objects | Subsets of connected grid points |

Union by rank vs by size | link |

Reference | YouTube: Disjoint Sets Data Structure – Weighted Union and Collapsing Find |

Reference | Wikipedia: Disjoint-set data structure |

**Top Questions**

Num | Problem | Summary |
---|---|---|

1 | Union find for weighted graph | LeetCode: Evaluate Division |

2 | Union find: connect groups and merge node count | LeetCode: Bricks Falling When Hit |

**Scenarios**

Union-find applications involve manipulating objects of all types:

Name | Summary |
---|---|

Computers in a network | |

Web pages on the Internet | |

Transistors in a computer chip | |

Variable name aliases | |

Pixels in a digital photo | |

Metallic sites in a composite system | |

Minimum spanning tree of a graph – Kruskal’s algorithm | |

What are the nodes and how to union nodes | LeetCode: Largest Component Size by Common Factor |

What nodes are? What edges are? | LeetCode: Sentence Similarity II, LeetCode: Regions Cut By Slashes |

Count node then initialize VS a fixed array | LeetCode: Satisfiability of Equality Equations |

Maintain a counter for group count | LeetCode: Graph Valid Tree |

Path compression to reduce levels | Keeps tree almost completely flat, and avoid tall trees |

Rank based merge | Balance by linking small tree below large one |

Collect result: add vs extract? | LeetCode: Most Stones Removed with Same Row or Column |

Get the nodes relationship quickly | LeetCode: Most Stones Removed with Same Row or Column |

How efficient unionfind vs DFS/BFS? | |

Time and space complexity of unionfind? |

**Code Skeleton**

// 1. Get node count. And initialize array with parent as itself // 2. Union: Connect two nodes, which is two groups essentially // 3. Find: find node's parent by value type DSU struct { parent []int } func constructor(size int) DSU { parent := make([]int, size) for i, _ := range parent { parent[i] = i } return DSU{parent:parent} } func (dsu *DSU) union(x, y int) { // TODO: rank based merge dsu.parent[dsu.find(y)] = dsu.find(x) } func (dsu *DSU) find(x int) int { // TODO: path compression for dsu.parent[x] != x { x = dsu.parent[x] } return x }

See all unionfind tree problems: #unionfind

- Review: Union Find Problems
- Leetcode: Sentence Similarity II
- Leetcode: Satisfiability of Equality Equations
- LeetCode: Regions Cut By Slashes
- Leetcode: Redundant Connection
- Leetcode: Path With Maximum Minimum Value
- Leetcode: Optimize Water Distribution in a Village
- Leetcode: Number of Islands II
- Leetcode: Number of Connected Components in an Undirected Graph
- Leetcode: Most Stones Removed with Same Row or Column

See more blog posts.