并查集

186


当需要判断大量数据是否有联系时,可以使用并查集。

将所有数据看作一棵棵单独的

每个树的根节点都是自己本身

如果两棵树有联系,我们就可以把其中一棵变成另一棵的叶子

这样, 只需要一个数组记录每个结点对应的根,只要两个结点的根相同,就说明他们在同一棵树上(有联系)



因为我们只需要知道根是谁,不需要知道这棵树上还有谁,因此,对于每棵树的叶子都直接连接到根上能够达到最快的访问速度



在访问的时候我们可以顺便进行一定程度的路径压缩

初始化时先把所有的uf[i]=i

连接时 uf[UF(a)] = UF(b);

这样就能把两个结点连到一棵树上(将a所在的树连接到b所在树的根上)

//并查集
int uf[maxn];
int UF(int n) {
    int t = uf[n];
    while(t != uf[t])
        t = uf[t];
    return uf[n] = t;
}
发布评论
  • 点击查看/关闭被识别为广告的评论