Union merges the sets, if not already merged, to which the given elements belong. It performs union by rank to keep the tree as flat as possible.
(p, q int)
| 44 | // Union merges the sets, if not already merged, to which the given elements belong. |
| 45 | // It performs union by rank to keep the tree as flat as possible. |
| 46 | func (u *UnionFind) Union(p, q int) { |
| 47 | rootP := u.Find(p) |
| 48 | rootQ := u.Find(q) |
| 49 | |
| 50 | if rootP == rootQ { |
| 51 | return |
| 52 | } |
| 53 | |
| 54 | if u.rank[rootP] < u.rank[rootQ] { |
| 55 | u.parent[rootP] = rootQ |
| 56 | } else if u.rank[rootP] > u.rank[rootQ] { |
| 57 | u.parent[rootQ] = rootP |
| 58 | } else { |
| 59 | u.parent[rootQ] = rootP |
| 60 | u.rank[rootP]++ |
| 61 | } |
| 62 | } |