# Union-Find Disjoint Set (UFDS)

UFDS is a straightforward but powerful data structure often used to determine when data is in the same set as one another

Type | Find(p) | Union(p, q) |
---|---|---|

Quick Find | O(1) | O(n) |

Quick Union | O(n) | O(n) |

Weighted union (union by rank) | O(log n) | O(log n) |

Path compression | O(log n) | O(log n) |

Weighted union + path compression | a(m, n) | a(m, n) |

parent = list(range(n + 1))

rank = [0] * (n + 1)

def find(p):

if p == parent[p]:

return p

parent[p] = find(parent[p])

return parent[p]

def union(p, q):

root_p = find(p)

root_q = find(q)

if rank[root_p] > rank[root_q]:

parent[root_q] = root_p

rank[root_p] += 1

else:

parent[root_p] = root_q

rank[root_q] += 1

Last modified 2mo ago