Union of two sets. set with bigger rank should be parent, so that the disjoint set tree will be more flat.
(x: Node, y: Node)
| 22 | |
| 23 | |
| 24 | def union_set(x: Node, y: Node) -> None: |
| 25 | """ |
| 26 | Union of two sets. |
| 27 | set with bigger rank should be parent, so that the |
| 28 | disjoint set tree will be more flat. |
| 29 | """ |
| 30 | x, y = find_set(x), find_set(y) |
| 31 | if x == y: |
| 32 | return |
| 33 | |
| 34 | elif x.rank > y.rank: |
| 35 | y.parent = x |
| 36 | else: |
| 37 | x.parent = y |
| 38 | if x.rank == y.rank: |
| 39 | y.rank += 1 |
| 40 | |
| 41 | |
| 42 | def find_set(x: Node) -> Node: |