POJ 1182 并查集

Description

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

Input

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

我是比如 A>B>C 对于每个点都有 P[X] V[X]表示他被谁打败了他打败了谁他们之间的关系处理好后比如A>B>C D>E>F 一旦 B 与E有关系在不出错的前提下然后处理好 AD BE CF之间的关系

#include <iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=50005;
int per[maxn],p[maxn],v[maxn],N,K;
int fa(int a){ return per[a]=per[a]==a?a:fa(per[a]);}
bool jud1(int X,int Y){
   if(X<1||Y<1||X>N||Y>N) return false;
   int fx=fa(X),fy=fa(Y);
   if(fx==p[fy]||fx==v[fy]||fy==p[fx]||fy==v[fx]) return false;
   per[fy]=fx;
   if(p[fx]!=0&&p[fy]!=0){  per[p[fy]]=p[fx];}
   if(p[fx]==0&&p[fy]!=0)p[fx]=p[fy];
   if(v[fx]!=0&&v[fy]!=0){  per[v[fy]]=v[fx];}
   if(v[fx]==0&&v[fy]!=0)  v[fx]=v[fy];
   if(p[fx]!=0){   p[p[fx]]=v[fx]; v[p[fx]]=fx;   }
   if(v[fx]!=0){   p[v[fx]]=fx; v[v[fx]]=p[fx];}
   return true;
}
bool jud2(int X,int Y){
     if(X<1||Y<1||X>N||Y>N) return false;
     int fx=fa(X),fy=fa(Y);
     if(fx==fy||fx==v[fy]||fy==p[fx]) return false;
    if(p[fy]!=0)per[p[fy]]=fx;
    if(v[fx]==0)v[fx]=fy;
    else per[fy]=v[fx];
    if(p[fx]!=0&&v[fy]!=0) per[v[fy]]=p[fx];
    if(p[fx]==0&&v[fy]!=0) p[fx]=v[fy];
    if(p[fx]!=0){ v[p[fx]]=fx;p[p[fx]]=v[fx];}
    if(v[fx]!=0){ p[v[fx]]=fx;v[v[fx]]=p[fx];} return true;
}
int main()
{
     scanf("%d%d",&N,&K);
          for(int i=0;i<=N;i++){
             per[i]=i; p[i]=v[i]=0;
          }
          int num=0;
        for(int i=0;i<K;i++){
             int D,X,Y;
             scanf("%d%d%d",&D,&X,&Y);
             switch(D){
              case 1: if(jud1(X,Y)==false) ++num; break;
              case 2: if(jud2(X,Y)==false) ++num; break;
             }
        }
        cout<<num<<endl;

    return 0;
}

View Code

还有一种方法带权并查集队友说也可以

当操作1 时判断

1 这两个点在同一个集合当中他们到达祖先的距离不同则出现错误相同就正确

2 这两个点不在同一个集合当中那么就得将这两个集合合并就是说 d[x]=（d[y]+d[fy])%3或者 d[y]=(d[x]+d[fx])%3 这样就保证了他们在一个集合当中的相同的位置我们在并查集中做了一点小动作保证了要修改的 d[fx] 或者d[fy] 为跟节点的子树能够将相应的位置进行相应的改变

当操作2 时判断

1 这两个的点在同一个集合当中他们到达祖先的距离(d[x]+1)必须等于d[y] 否则就出现错误（因为我们保证了小的距离吃大的距离自然最后记得模三）

2 这两个点在不懂得集合当中那么也必须得河滨这两个集合就是说 (d[x]+1)%3==(d[y]+d[fy])%3 可以推得 (d[x]+1-d[y]+3)==d[fy] 这样也保证了这两个点在相对的位置

#include <iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=50005;
int per[maxn],d[maxn];
int fin(int a){
  if(per[a]==a)return a;
  int t=per[a];
      per[a]=fin(per[a]);
   d[a]=(d[a]+d[t])%3;
   return per[a];
}
bool unionnode(int D,int x,int y){
      int fx=fin(x),fy=fin(y);
      if(D==1){
          if(fx==fy){  return d[x]==d[y]?true:false;    }
          if(d[x]==d[y]){  per[fy]=fx;return true;}
          if(d[x]>d[y]){ d[fy]=(d[x]-d[y])%3;per[fy]=fx; return true; }
          d[fx]=(d[y]-d[x])%3; per[fx]=fy; return true;
      }
      if(fx==fy){   return ((d[x]+1)%3)==d[y]?true:false;  }
      d[fy]=(d[x]-d[y]+1+3)%3;
      per[fy]=fx;
      return true;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++){
        per[i]=i;d[i]=0;
    }
    int num=0;
    while(k--){
         int a,b,c;
         scanf("%d%d%d",&a,&b,&c);
         if(b>n||c>n||!unionnode(a,b,c)) num++;
    }
    printf("%d
",num);
    return 0;
}

View Code