根据题意有三种分类:ABC,要求检查双向关系的矛盾与否,可以用带权并查集实现。
令d[x]表示x到px的距离,在路径压缩时更新dx:
int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
那么同一根节点下的两个节点:
-
如果同类,他们到根节点的距离mod3相同。
-
如果x吃y,规定x为y的子结点,则dx=dy+1
于是对于x和y的关系:
- 如果x和y在一个根节点上
- 同类,则dx=dy(mod 3)
-
不同类,则dx≠dy(mod 3)
-
不在同一个根节点上,进行合并操作:
- x与y同类:
- 将px的根节点嫁接到py,
p[px] = py
- 此时dx表示x到合并前px的距离,而到现在根节点py的距离应该为dx+dpx,且满足dx+dpx=dy(mod3),所以
d[px] = (dy-dx)mod3
- 将px的根节点嫁接到py,
- x吃y:
- 将px的根节点嫁接到py,
p[px] = py
- 此时dx表示x到合并前px的距离,而到现在根节点py的距离应该为dx+dpx,且满足dx+dpx=dy+1(mod3),所以
d[px] = (dy+1-dx)mod3
- 将px的根节点嫁接到py,
同类型还有奇偶游戏,可以得到分为x类就mod x。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 5e4+5;
int n,k,p[MAXN],d[MAXN],cnt = 0;
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++) p[i] = i,d[i] = 0;
for(int i = 1;i <= k;i++)
{
int o,x,y;scanf("%d%d%d",&o,&x,&y);
if(x > n || y > n) cnt++;
else
{
int px = find(x),py = find(y);
if(o == 1)// d[x] = d[y] (mod 3)
{
if(px == py && (d[x]-d[y])%3) cnt++;
else if(px != py)
{
p[px] = py;
d[px] = d[y]-d[x];// dx+d[px] = dy (mod3)
}
}
else// dx%3 = dy%3+1
{
if(px == py && (d[x]-d[y]-1)%3) cnt++;
else if(px != py)
{
p[px] = py;
d[px] = d[y]+1-d[x];// (dx+d[px]-dy)%3 = 1;
}
}
}
}
printf("%d",cnt);
return 0;
}