5,323
edits
Interview Algorithms: Difference between revisions
→Data Structures
| Line 92: | Line 92: | ||
===Segment Trees=== | ===Segment Trees=== | ||
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree] | See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree] | ||
===Union Find=== | |||
In Union Find, you build a tree where each tree represents a set.<br> | |||
Your given a pair of relations where (a, b) indices a and b are in the same set.<br> | |||
The ''Union'' operation places a and b in the same set by attaching the root of b to the root of a. | |||
The ''Find'' operation recursively looks up the parent of a to find the root of the tree of a. | |||
<syntaxhighlight lang="python"> | |||
parents = {} | |||
def find(a): | |||
while parents[a] != a: | |||
a = parents[a] | |||
return a | |||
for (a, b) in relations: | |||
if a not in parents: | |||
parent[a] = a | |||
a_root = find(a) | |||
if b not in parents: | |||
parent[b] = b | |||
b_root = find(b) | |||
parents[b_root] = a_root # Attach b_root to a_root | |||
</syntaxhighlight> | |||
==Misc Tricks== | ==Misc Tricks== | ||