题目链接：点击打开链接
思路：参考资料后，两种方法：①就是开3倍空间，然后和普通并查集一样，但是关系不太好理解。②向量偏移
方法一：有好几种理解方式，还是书上的好理解：
| x-A | x-B |
x-C |
| y-A | y-B | y-C |
AC代码：
代码断点1处的 是判断是否b和c不是同类。那么不是同类怎么表示：
判断x-A 和 y-B 是不是一组，x-A 和 y-C是不是一组。是的话矛盾ans++；
如果不矛盾，就说明是同类，就合并x-A和y-A ， x-B和y-B， x-C和y-C；
代码断点2处的是判断b是否能吃c，先看是否矛盾，怎么表示矛盾呢：
首先题目意思：A吃B，B吃C，C吃A。
矛盾的原因有两个：①同类，②不是同类，但是不符合题目要求；
例如代码中的 if(findfather(b+n) == findfather(c+n) || findfather(b+2*n) == findfather(c+n))
这个是判断 是否【b和c都是 B】 或者 【b是C，c是B】这就是对的，因为起到了反例的效果。（说的b吃c，但是C不吃B）
这个条件只要前面是同类 后面是 吃的反例就是对的。
例如 if(findfather(b) == findfather(c) || findfather(b+n) == findfather(c))
是否【b和c都是A】或者【b是B，c是A】也是反例，（说的b吃c，但是B不吃A）
#include<stdio.h>
int father[200000];
const int maxv=50010;
void intit() {
for(int i=0; i<=200000; i++) {
father[i]=i;
}
}
int findfather(int x) {
int a=x;
while(father[x]!=x) {
x=father[x];
}
while(a!=father[a]) {
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
void Union(int a,int b) {
int fa=findfather(a);
int fb=findfather(b);
if(fa!=fb) {
father[fa]=fb;
}
}
int main() {
int n,m,a,b,c,ans=0;
scanf("%d%d",&n,&m);
intit();
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&a,&b,&c);
if(b < 0 || b > n || c < 0 || c > n || (a == 2 && (b == c))) {//条件
ans++;
continue;
}
if(a==1) {//代码断点1
if(findfather(b)==findfather(c+n)||findfather(b)==findfather(c+2*n)) {
ans++;
continue;
}
else {
Union(b, c);
Union(b+n, c+n);
Union(b+2*n, c+2*n);
}
}
if(a==2) {//代码断点2
if(findfather(b+n) == findfather(c+n) || findfather(b+2*n) == findfather(c+n)) {
ans++;
continue;
} else {
Union(b, c+n);
Union(b+n, c+2*n);
Union(b+2*n, c);
}
}
}
printf("%d",ans);
}
方法二：向量偏移；
参考博客：https://blog.csdn.net/freezhanacmore/article/details/8767413
之所以叫向量偏移是和向量有关，体现在合并函数
先看看find函数：a和b的关系r1， b和c的关系r2，那么a和c的关系为（r1+r2）% 3
打表可以推断出来，（具体参考上面博客）
再看Union函数，fy合并于fx，那么fy对于fx的关系见下图
即 r[fy] = ( -r[y] + (d-1) + r[x])
推导：设d = 1，y和x同类，y对x关系为0
设d = 2, x吃y，那么y对x的关系为1， x对y的关系为2
无论d是多少，y对x的关系都是d-1
图片中的向量关系可以得出,这就是向量偏移
可以和我的另一篇对比看一看：https://blog.csdn.net/qq_40932661/article/details/81043876
AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 50010;
int father[MAXN];
int flag[MAXN];
int n, m, op, u, v, ans;
//没有用rank数组，可能是因为合并时时固定的，我用rank数组优化，会错
void init(int n) {
for(int i = 0; i <= n+1; i++) {
father[i] = i;
flag[i] = 0;
}
}
int find(int x) {
if(x == father[x])
return x;
int xx = father[x];
father[x] = find(father[x]);
flag[x] = (flag[x] + flag[xx]) % 3;// %集合数
return father[x];
}
void Union(int x, int y) {
int fx = find(x);
int fy = find(y);
if(fx == fy)
return;
father[fy] = fx;
flag[fy] = (flag[x] - flag[y] + 3 + (op-1)) % 3;//这个看对应关系。 注意fx，fy，x，y
}
int main() {
scanf("%d%d", &n,&m);
init(n);
ans = 0;
while(m--) {
scanf("%d%d%d", &op, &u, &v);
if(u <= 0 || u > n || v <= 0 || v > n || (op == 2 && u == v)) {
ans++;
continue;
}
if(find(u) == find(v)) {
if((op-1) != (flag[v]-flag[u]+3)%3)//谁减谁，要对应Union操作，这里（father[fy] = fx）,换了也可以 。这里特别要注意
ans++;
continue;
}
Union(u, v);
}
printf("%d
", ans);
}