POJ 1182 并查集

#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;
}