Review: Union Find Problems Posted on August 14, 2019November 16, 2019 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 Reference YouTube: Disjoint Sets Data Structure – Weighted Union and Collapsing Find Scenarios Union-find applications involve manipulating objects of all types: 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 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 UF struct { parent []int } func constructor(size int) UF { parent := make([]int, size) for i, _ := range parent { parent[i] = i } return UF{parent:parent} } func (uf *UF) union(x, y int) { // TODO: rank based merge uf.parent[uf.find(y)] = uf.find(x) } func (uf *UF) find(x int) int { // TODO: path compression for uf.parent[x] != x { x = uf.parent[x] } return x } Questions Name Example 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 Union find for weighted graph Leetcode: Evaluate Division Union find: connect groups and merge node count Leetcode: Bricks Falling When Hit How efficient unionfind vs DFS/BFS? Time and space complexity of unionfind? CheatSheet: Leetcode For Code Interview See all unionfind tree problems: #unionfind Review: Union Find ProblemsLeetcode: Sentence Similarity IILeetcode: Satisfiability of Equality EquationsLeetcode: Redundant ConnectionLeetcode: Path With Maximum Minimum ValueLeetcode: Number of Islands IILeetcode: Number of Connected Components in an Undirected GraphLeetcode: Most Stones Removed with Same Row or ColumnLeetcode: Lexicographically Smallest Equivalent StringLeetcode: Graph Valid Tree See more blogposts. Post Views: 0