路径压缩
如下图
上面变成下面
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5+10;
int a[N],p[N],d[N];
int find(int x)
{
if(p[x]!=x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
int res;
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
p[i] = i;//初始化,每个节点
}
for(int k = 1;k<=m;k++)
{
int t,x,y;
cin>>t>>x>>y;
if(x > n || y> n)res++;//超过直接错
else
{
int rx = find(x),ry = find(y);//路径压缩(函数内递归),使得父节点就是祖宗节点
if(t == 1)//x与y是同类
{
if((abs(d[y] - d[x]))%3 && rx ==ry) res++;//如果已经在路径上了,但是不符合距离为同类,即%3 == 0,则是错的
else if(rx!=ry)//如果不是路径里的
{
p[rx] = ry;
d[rx] = d[y] - d[x];
}
}
else
{
if(x == y) res++;// 相同的不能吃
else if(rx == ry && abs(d[x] - d[y] -1) % 3) {res++;}
else if(rx != ry)
{
p[rx] = ry;
d[rx] = d[y] - d[x] +1;
}
}
}
}
cout<<res;
return 0;
}