Burnling's Blog
0%

并查集

发表于 更新于

  • 并查集有两种操作——查询，合并。

    查询通常用来求联通块中各节点的父节点。

    而合并则可统一两点的父节点。

  • 初始化

    1
    2
    3
    4
    5
    int f[N];
    for(int i = 0;i<n;i++){
        //每个元素都是单独的一个集合，则他们的根都是自己
        f[i] = i;
    }

  • 查询x的根节点

    1
    2
    3
    int find(int x){
        return f[x] == x ? x : (f[x]=find(f[x]));
    }

    这个三目表达式

    f[x] == x，判断x的父节点是不是他自己，如果是，x就是根可以返回

    find(f[x])，若x还有父亲，则查找x的父亲的父亲，直到有一个点的父亲是自己

    f[x] = find(f[x])，便于后续找根：将x的父亲重置为x的父亲的父亲，最终x的父亲就是x的根

  • 合并

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //其实不用刻意写函数，直接在主函数中写亦可
    void unionSet(int x, int y) {
    	x = find(x);
    	y = find(y);
        //若x与y有共同的根，说明x和y在同一个集合里
    	if (x == y) return;
        //令x和y有相同的根
    	fa[x] = y; 
    	return;
    }