萌新第一次写带权并查集的题目
求助给我大佬讲一下
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N],vis[N];
int n,k;
int ans=0;
int find(int a)
{
if (a!=f[a])
{
int fa=find(f[a]);
vis[a]=(vis[a]+vis[fa])%3;
return f[a]=fa;
}
return f[a];
}
bool m(int num,int a,int b)
{
int fa=find(a),fb=find(b);
if(num==1)
{
if(fa==fb and vis[a]!=vis[b])
{
return false;
}
if(fa!=fb)
{
f[fa]=fb;
vis[fa]=(3-vis[a]+vis[b])%3;
return true;
}
}
if(fa==fb)
{
if(abs(vis[a]-vis[b])%3!=1)
{
return false;
}
}
f[fa]=fb;
vis[fa]=(3-vis[a]+vis[b]+1)%3;
return true;
}
int main()
{
cin>>n>>k;
int num,x,y;
for(int i=1;i<=n;i++) f[i]=i,vis[i]=0;
for(int i=1;i<=k;i++)
{
cin>>num>>x>>y;
if(x>n or y>n or (num==2 and x==y) or !m(num,x,y))
{
ans++;
continue;
}
}
cout<<ans;
}
求助!