This implementation uses weighted quick union by rank with path compression by halving.
| 77 | /// This implementation uses weighted quick union by rank |
| 78 | /// with path compression by halving. |
| 79 | pub struct UF { |
| 80 | parent: Vec<usize>, // parent[i] = parent of i |
| 81 | // rank[i] = rank of subtree rooted at i (never more than 31) |
| 82 | // rank == 31的话，将有 2 ^ 31 个节点, 一棵满二叉树的节点数量 |
| 83 | rank: Vec<usize>, |
| 84 | count: usize, // number of components |
| 85 | } |
| 86 | |
| 87 | impl QuickFindUF { |
| 88 | pub fn new(n: usize) -> Self { |
nothing calls this directly
no outgoing calls
no test coverage detected