Review: Union Find Problems

Union find is helpful to build relationship among different sets

Key operations: union, find, etc.



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
}

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

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

Ideas

Name Example
What nodes are? What edges are? Leetcode: Sentence Similarity II
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  
Rank based merge  

Questions

Name Summary
How efficient unionfind vs DFS/BFS?  
Time and space complexity of unionfind?  

See all unionfind tree problems: #unionfind

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.