POJ2492 A Bug's Life 带权并查集

分析：所谓带权并查集，就是比朴素的并查集多了一个数组，记录一些东西，例如到根的距离，或者和根的关系等

这个题，权数组为relation 代表的关系  1 和父节点不同性别，0，和父节点同性别

并查集一个很大的方便在于它可以进行路径压缩,可以将树高维持在2（当然有一些其它应用是不需要路径压缩的）

这就需要在路径压缩的时候，随之得到一个节点和树根的关系,这样我们可以通过路径中的父子关系，递归得到根节点和当前结点的关系

已知每个点和根节点的关系，那么任意两个点关系也很容易得到（这就是路径压缩的意义）

这需要设计一个路径压缩算法，对于此题是 relation[x]=(relation[x]+relation[t])%2;

当需要合并两个集合时，我们要合并两个根节点，由于我们得到了每个节点和根节点关系，

所以根据当前的关系，很容易将两个根节点合并，此题是 relation[x]=(relation[u]-relation[v]+1)%2;

总结：其实这题和经典并查集食物链那道题是一样的，只不过简单的多

带权并查集的应用 关键在于

1：权值数组代表什么

2：设计方便的路径压缩算法

3：搞清楚合并时的树根关系

#include <stdio.h>

#include <cstring>

const int N=2e3+;

int fa[N],n,m,T;

int relation[N];

int find(int x){

  if(x==fa[x])return x;

  int t=fa[x];

  fa[x]=find(fa[x]);

  relation[x]=(relation[x]+relation[t])%;

  return fa[x];

}

void Union(int u,int v){

   int x=find(u),y=find(v);

   fa[x]=y;

   relation[x]=(relation[u]-relation[v]+)%;

}

int main()

{

    int cas=;

    scanf("%d",&T);

    while(T--){

       printf("Scenario #%d:\n",++cas);

       scanf("%d%d",&n,&m);

       for(int i=;i<=n;++i)fa[i]=i,relation[i]=;

       bool flag=;

       while(m--){

         int u,v;

         scanf("%d%d",&u,&v);

         if(find(u)==find(v)){

            if(relation[u]==relation[v])flag=;

         }

         else Union(u,v);

       }

       if(flag)printf("Suspicious bugs found!\n\n");

       else printf("No suspicious bugs found!\n\n");

    }

    return ;

}