柒葉灬 的博客

柒葉灬 的博客

并查集进阶(个人笔记7)

posted on 2018-08-27 22:12:01 | under 技巧篇 |

巧用并查集


  • 1.并查集可以处理的信息十分有限,它只能处理点到根的信息,切修改后不能撤回。

  • 2.用并查集收集子树信息:

    void dfs(int f,int x){
    fa[x]=x;
    vis[x]=1;
    
    for(int i=0;i<query[x];i++){
        int y=query[x][i].to;
        if(vis[y])solve(x,y);
        //表示已经访问到了
    }
    
    for(int i=0;i<T[x].size();i++){
        int y=T[x][i];
        .......;
    }
    
    fa[x]=f;
    
    return;
    }
  • 3.如果把并查集和其他数据结构相比,可以看到,

    int getfa(int x){
    if(fa[x]!=x){
        int t=fa[x];
        fa[x]=getfa(fa[x]);
        添加信息;
    }
    return fa[x];
    }

    是不是很像延迟更新(lazy标记)?所以如果有类似询问区间的题目,把左端点挂到右端点,就可以离线进行回答。

  • 4.例题,“最优贸易简易版”。

END