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 |

**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 |

**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? |

See all unionfind tree problems: #unionfind

- Review: Union Find Problems
- Leetcode: Sentence Similarity II
- Leetcode: Satisfiability of Equality Equations
- Leetcode: Redundant Connection
- Leetcode: Path With Maximum Minimum Value
- Leetcode: Number of Islands II
- Leetcode: Number of Connected Components in an Undirected Graph
- Leetcode: Most Stones Removed with Same Row or Column
- Leetcode: Lexicographically Smallest Equivalent String
- Leetcode: Largest Component Size by Common Factor

See more blog_{posts}.