poj 1182（注意合并操作中relation的计算）

/*
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5
*/
#include
using namespace std;
#define maxn 50005
struct node{
    int parent;
    int relation;
}p[maxn];
int find(int x){
    if(p[x].parent==x)
        return x;
    int tmp = p[x].parent;
    p[x].parent = find(tmp);
    p[x].relation = (p[x].relation+p[tmp].relation)%3;
    return p[x].parent;
}
int main(){
    int n,k,num = 0,d,r,s;
    scanf("%d%d",&n,&k);
    for(int i=1;i1;i++){
        p[i].parent = i;
        p[i].relation = 0;
    }
    while(k--){
        scanf("%d%d%d",&d,&r,&s);
        if(r>n||s>n){
            num++;
            continue;
        }
        if(d==2&&r==s){
            num++;
            continue;
        }
        int px = find(r);
        int py = find(s);
        if(px!=py){
            p[px].parent = py;
            p[px].relation = (d-1+p[s].relation-p[r].relation+3)%3; //搁置 
        }
        else{
            if(d==1&&p[r].relation!=p[s].relation){
                num++;
                continue;
            }
            if(d==2&&(p[r].relation-p[s].relation+3)%3!=1){//搁置
                 num++;
                continue;
            }
        }
    }
    printf("%d\n",num);
    return 0;
}