Review: Union Find Problems Posted on August 14, 2019March 22, 2020 by braindenny 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 } CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups See all unionfind tree problems: #unionfind Review: Union Find ProblemsLeetCode: Validate Binary Tree NodesLeetcode: Sentence Similarity IILeetcode: Satisfiability of Equality EquationsLeetCode: Regions Cut By SlashesLeetcode: Redundant ConnectionLeetcode: Path With Maximum Minimum ValueLeetcode: Optimize Water Distribution in a VillageLeetcode: Number of Islands IILeetcode: Number of Connected Components in an Undirected Graph See more blog posts. Post Views: 0