主要考察加权并查集

更加深入的考察并查集知识，在并查集中加入关系域，关系域会随着加入数据的内容进行实时更新。 c++代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e8+7;
int n,k;
int d,x,y;
int h[N];
long long sum=0;
struct m{
    int parent;
    int relation;
}p[N];
int find_root(int root){
    int temp;
	if(root == p[root].parent)
		return root;
	temp = p[root].parent; //路径压缩
	p[root].parent = find_root(temp);
	p[root].relation = (p[root].relation + p[temp].relation) % 3; //关系域更新
	return p[root].parent; //根结点
}
int main ()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        p[i].parent=i;
        p[i].relation=0;
    }
    while(k--){
        cin>>d>>x>>y;
        if(x>n||y>n){
            sum++;continue;
        }
        if(d==2&&x==y){
            sum++;continue;
        }
        int root1 = find_root(x);
		int root2 = find_root(y);
        if(find_root(x)!=find_root(y)){
            p[root2].parent=root1;
            p[root2].relation=(3+(d-1)+p[x].relation-p[y].relation)%3;
        }
        else{
            if(d==1&&p[x].relation!=p[y].relation){
                sum++;continue;
            }
            if(d==2&&((3-p[x].relation+p[y].relation)%3!=d-1)){
                sum++;continue;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}