另一个题解写了拆点并查集的做法，我这里再写一下带权并查集的做法
本题的关系有三层 -> a -> b -> c -> ，但不同的是本题的关系是有向的，也就是说a和b如果是敌对关系，那么b和a就不是敌对关系。
关系传递的本质实际上是向量的运算。
还是设 d[x] 表示 x 与 fa[x] 的关系，0 代表是同类，1 代表是x吃fa[x], 根据关系图自然2就代表x被fa[x]吃。
下面假设a的祖先是x，b的祖先是y，为简化书写，设他们的向量关系为
→a=(a,x)→b=(b,y)
给出的关系设为rel=→ab
以下的向量关系均用以上符号代替，实际运算时自行带入二元组运算即可
-
若x=y
想要知道 →ab ，则需要 →a−→b 然后对3取模并移动到正整数
此时得到的关系0代表ab是同类，1代表a吃b，2代表a被b吃。直接与rel进行比较即可。 -
如果x和y不等，那么这个给出的关系肯定是合法的
合并的时候同样fa[x] = y，→x=→b+→ab−→a
然后就可以愉快的搞了
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 233;
int fa[maxn], d[maxn];
int ff(int x)
{
if(fa[x] == x) return x;
int r = ff(fa[x]);
d[x] += d[fa[x]];
return fa[x] = r;
}
int main()
{
int n,k; cin >> n >> k;
for(int i = 0; i <= n; i++) fa[i] = i;
int ans = 0;
for(int i = 1; i <= k; i++)
{
int t, a, b;
scanf("%d%d%d", &t, &a, &b);
if(a > n || b > n) {ans ++; continue;}
else if(t == 2 && a == b) {ans++; continue;}
else
{
int rel;
if(t == 2) rel = 1;
else rel = 0;
int x = ff(a), y = ff(b);
if(x == y)
{
if((((d[a] - d[b]) % 3) + 3) % 3 != rel)
ans++;
}
else
{
fa[x] = y;
d[x] = d[b] - (d[a] - rel);
}
}
}
cout<< ans;
}
请问大佬们%%%是什么暗语❓
这个符号是模的意思
就是膜拜大佬
膜拜膜拜膜拜
%%%
🆗🆗
%%%
%%%
%%%
%%%
%%%
%%%
借楼，粘个跟算法提高课相似的代码解法
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 5e4 + 10; int n, m; int p[N], d[N]; int find(int x) { if (p[x] != x) { int root = find(p[x]); d[x] = (d[x] + d[p[x]]) % 3; p[x] = root; } return p[x]; } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) p[i] = i; int res = 0; for (int i = 1; i <= m; i ++ ) { int t, a, b; cin >> t >> a >> b; int pa = find(a), pb = find(b); int temp = 0; if (t == 2) temp = 1; //有几个关系就%几个 if (a > n || b > n) res ++; else if (pa == pb && ((d[a] - d[b]) % 3 + 3) % 3 != temp) { res ++; } else if (pa != pb) { p[pa] = pb; d[pa] = d[b] - d[a] + temp; } } cout << res << endl; return 0; }“如果x和y不等，那么这个给出的关系肯定是合法的
合并的时候同样fa[x] = y，x =b +ab−a“
这个d[x]是怎么推出来的呀？求解
“关系传递的本质实际上是向量的运算”，死去的离散数学知识开始攻击我🤣
%%%
if((((d[a] - d[b]) % 3) + 3) % 3 != rel),大佬请问这句是怎么算的，什么意思？ 我数学不太好😂
第一个模三是保证三种，第二个加三模三是确保得到的值是一个正数
我佬~，看不懂
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
orZ
orz %%%
为啥这个fa的初始化是a啊
太神仙了
%%%%
d[px] = d[y] - d[x]; //(d[x]+d[px]-d[y])%3==0这个不是很理解，不是求 d [ x ] 或者 d [ y ] 到节点 0 的距离吗？为什么是求 d [ px ]呢？
这是因为，当x和y不在一棵树上，需要把x的根节点插到y上，同时要保持x和y的关系，而在find函数里用到的d[]的算法是需要知道d[px]的大小的，因此在此需要保证，给d[px]正确赋值确保下次用find 函数不会出错。这里其实作减法就是手动确保了x和y的关系可以通过x的根节点来传递。
虽然看不懂，还是觉得很厉害的样子
我天，大佬%%%，我看了好久，发现得把向量这个概念带进去，然后画个图就好理解了（已经看了好久了|）
int r=find(f[x]);
d[x]+=d[f[x]];
return f[x]=r;
和
d[x]+=d[f[x]];
return f[x]=find(f[x]);
有什么区别吗
find(f[x]) 先做了一次路径压缩，对压缩后的并查集再求新关系。你第二种写法是先求关系再压缩，此时x的father不一定是原来那个了。
%%%%%%%
%%%5
int r = ff(fa[x]);
d[x] += d[fa[x]];
return fa[x] = r;
这个为什么不可以合一起写成这样。
d[x] += d[fa[x]];
return fa[x] = ff( fa[x] ) ;
find(f[x]) 先做了一次路径压缩，对压缩后的并查集再求新关系。你第二种写法是先求关系再压缩，此时x的father不一定是原来那个了。