trie 树怎么并查集合并
  • 板块学术版
  • 楼主typerxiaozhu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/31 17:31
  • 上次更新2024/7/31 19:22:00
查看原帖
trie 树怎么并查集合并
807832
typerxiaozhu楼主2024/7/31 17:31

各位佬,我正在尝试用并查集合并 trie 树上的点,但是有个地方不理解,为什么最后要写 y = find(y),修改子树对 y 有什么影响吗

void merge(int x, int y)
{
    if (x == y) return; //已经在同一集合就跳过
    fa[x] = y; //将 x 合并到 y 
    st[y] |= st[x]; //访问不到之后把之前的答案挂到 y 上
    //合并 x, y 的子树
    for (int i = 0; i <= 9; i++)
    {
        int a = son[x][i], b = son[y][i];
        int pa = find(a), pb = find(b);
        //由于我们将 x 合并到 y,所以如果 y 下面没有了,要加过去
        if (!b) son[y][i] = pa;
        else if (a) merge(pa, pb), y = find(y); 
    }
}
2024/7/31 17:31
加载中...