当需要判断大量数据是否有联系时,可以使用并查集。
将所有数据看作一棵棵单独的树
每个树的根节点都是自己本身
如果两棵树有联系,我们就可以把其中一棵变成另一棵的叶子
这样, 只需要一个数组记录每个结点对应的根,只要两个结点的根相同,就说明他们在同一棵树上(有联系)
因为我们只需要知道根是谁,不需要知道这棵树上还有谁,因此,对于每棵树的叶子都直接连接到根上能够达到最快的访问速度
在访问的时候我们可以顺便进行一定程度的路径压缩
初始化时先把所有的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; }