学步园

并查集最多就加个rank、和附加信息

rank一定表示节点 u 和 fa[u] 的关系

附加信息一般就有size（sz）、sum。。。

首先，初始化并查集 initset

void initset()
{
     for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
     //初始化rank
     //初始化附加信息
}

find 函数：

int find(int x)
{
     if(fa[x]==x) return x;
     int tmp=fa[x];
     fa[x]=find(fa[x]);//此时fa[x]为祖先
     //更新rank：根据x和其父亲tmp的关系和tmp和祖先fa[x]的关系更新x和fa[x]的关系
     //更新附加信息
     return fa[x];
}

合并，unio

void unio(int a,int b)
{
     int u=find(a),v=find(b);
     if(u!=v)
     {
          if(sz[u]<sz[v]) fa[u]=v;//极端数据
          else            fa[v]=u;
          sz[u]=sz[v]=sz[u]+sz[v];
          //更新rank
          //更新附加信息
     }
}

现在对付裸的并查集像食物链可以秒了

如果可以把集合分为两个部分的话，可以考虑互斥几何（是相对的） ，参考wikioi 1069

（以下部分文章删了）

并查集的扩展：

集合 set

现在并查集多了个新功能：删点

离线处理：

拆分集 cut

bzoj 1015 星球大战

并查集的应用：

关押罪犯、并查集某某题。。。

还有一类题

scoi 游戏

POI 2008 CLO