并查集

作者：

water-lover , 2020-08-10 21:41:02 , 所有人可见 , 阅读 662

1. 将两个集合合并
2. 询问两个元素是否在一个集合当中

每个集合用一棵树来表示，树根的编号就是整个集合的编号每个节点存储它的父节点，p[x]表示x的父节点

1. 如何判断树根： if(p[x] == x) 则为树根;
2. 如何求x的集合编号：while(p[x] != x) x = p[x];

int find(int x){//返回x的祖宗结点 + 路径压缩
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}