并查集

当需要判断大量数据是否有联系时，可以使用并查集。 将所有数据看作一棵棵单独的树 每个树的根节点都是自己本身 如果两棵树有联系，我们就可以把其中一棵变成另一棵的叶子 这样， 只需要一个数组记录每个结点对应的根，只要两个结点的根相同，就说明他们在同一棵树上(有联系) 因为我们只需要知道根是谁，不需要知道这棵树上还有谁，因此，对于每棵树的叶子都直接连接到根上能够达到最快的访问速度 在访问的时候我们可以顺便进行一定程度的路径压缩 初始化时先把所有的 uf[i]=i 连接时 uf[UF(a)] = UF(b); 这样就能把两个结点连到一棵树上(将a所在的树连接到b所在树的根上) ```cpp //并查集 int uf[maxn]; int UF(int n) { int t = uf[n]; while(t != uf[t]) t = uf[t]; return uf[n] = t; } ```