另一个题解写了拆点并查集的做法，我这里再写一下带权并查集的做法
本题的关系有三层 -> 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，为简化书写，设他们的向量关系为
$\vec{a} = (a,x) \quad \vec{b} = (b,y)$
给出的关系设为$rel = \vec{ab}$
以下的向量关系均用以上符号代替，实际运算时自行带入二元组运算即可
-
若$x = y$
想要知道 $\vec{ab}$ ，则需要 $\vec{a} - \vec{b}$ 然后对3取模并移动到正整数
此时得到的关系0代表ab是同类，1代表a吃b，2代表a被b吃。直接与rel进行比较即可。 -
如果x和y不等，那么这个给出的关系肯定是合法的
合并的时候同样fa[x] = y，$\vec{x} = \vec{b} + \vec{ab} - \vec{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;
}
请问大佬们%%%是什么暗语❓
这个符号是模的意思
就是膜拜大佬
膜拜膜拜膜拜
%%%
🆗🆗
%%%
%%%
%%%
%%%
%%%
借楼，粘个跟算法提高课相似的代码解法
“如果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 [ 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不一定是原来那个了。