直接看题:https://www.acwing.com/problem/content/description/242/
下面就是代码的实现了,因为自己与自己肯定是同类我们初始化为0.
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,k;
int fk,x,y;
int fa[100010],d[100010];
int find(int x)
{
if(fa[x]!=x)
{
int t=fa[x];
fa[x]=find(fa[x]);
d[x]+=d[t];
}
return fa[x];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) fa[i]=i;
int res=0;
while(k--)
{
cin>>fk>>x>>y;
if(x>n||y>n) res++;
else if(fk==1)
{
int x1=find(x),y1=find(y);
if(x1==y1&&(d[x]-d[y])%3) res++;
else if(x1!=y1)
{
fa[x1]=y1;
d[x1]=d[y]-d[x]+3;
}
}
else{
int x1=find(x),y1=find(y);
if(x1==y1&&(d[x]-d[y]-1)%3) res++;
else if(x1!=y1)
{
fa[x1]=y1;
d[x1]=d[y]-d[x]+4;
}
}
}
cout<<res;
}