POJ 1182-権限を持ってセットを調べる

重み付きパラレルチェックセットは、1つのfa配列を維持する以外に、1つのrank配列を維持することであり、2つの意味があり、1つはパス圧縮時のエッジの重み値であり、もう1つは現在の点とルートノードの相対関係である.この問題が明らかに考察されたのは
ルートノードと現在のノードの相対関係はrank【x】=0,1,2にA,B,Cの3種類の動物を表し,最初はすべての動物のrank値が0であり,まだ関係を手配していないことを示し,
文の入力では、1 xyはx、yを同じ値に、2 xyはrank【x】+1=rank【y】を表すが、ここではyのrankの値を直接変えるのではなく、yが存在するルートノードのrank値を変える.
関係を立てて、yと1つの集合内の動物はすべてxと関係を創立して、このように根のノードのrankを変えてやっとすべての動物のrankがすべて更新されることを保証することができて、xの所在する集合とyの所在する集合が関係を創立していないためです
以前、x,yの関係は任意であってもよい.
1 xyを入力すると、まずx,yが1つの集合内にあるかどうかを見て、x,yの間が絶対的な関係であれば、rank【x】とrank【y】の大きさで文の正確性を判断することができ、そうでなければx,yの間には
確定した関係であれば、この文は正しいです.rank【y】が存在する集合のルートノードのrank値を修正します.
2 xyを入力する場合と1 xyを入力する場合は同じです.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#define N 100005
#define lc rt<<1
#define rc rt<<1|1
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e4 + 10;

int n,k;
int d,x,y;
int fa[maxn];
int rank[maxn];

int find(int x)
{
    if(fa[x] == x)
    return x;
    int p = find(fa[x]);
    rank[x] = (rank[fa[x]] + rank[x])%3;
    return fa[x] = p;
}

int main()
{
     //freopen("in","r",stdin);
     int cnt = 0;
     scanf("%d%d",&n,&k);
     for(int i = 0; i < n; ++i) fa[i] = i;

     memset(rank,0,sizeof(rank));
     for(int i = 0; i < k; ++i)
     {
         scanf("%d%d%d",&d,&x,&y);
         if(x > n||y > n||(d == 2&&x == y)) {
             cnt++;continue;}
         int s1 = find(x),s2 = find(y);//    
         if(d == 1){
             if(s1 == s2){
                 if(rank[x] != rank[y]) cnt++;
             }
             else {
                 rank[s2] = (rank[x] - rank[y] + 3)%3;//  y    ，      s2；
                 fa[s2] = s1;//  x   y     ；
             }
         }
         else if(d == 2)
         {
             if(s1 == s2) {
                 if((rank[x] + 1)%3 != rank[y]) cnt++;
             }
             else {
                 rank[s2] = (rank[x] + 1 - rank[y] + 3)%3;//  
                 fa[s2] = s1;
             }
         }
         //printf("%d %d
",i,cnt);
     }
     printf("%d
",cnt);
}