看了看前面dalao们的题解
感觉
为什么要把简单的问题复杂化啊
居然还有人用向量orz
这道题还是用维护到根节点距离的并查集最简洁啊
虽然不是很好想到
但是向量和带权并查集什么的不是更不好想吗
难道是dalao们恶意虐菜?
//来自算法基础课
维护到根节点距离的并查集
一、初始化
void init() {
for(register int i=1; i<=n; i++) {
fa[i] = i;
d[i] = 0;
}
}
二、找祖源
int find(int x) {
if(fa[x]==x) return x;
else {
int last = fa[x];
fa[x] = find(fa[x]);
d[x] += d[last];
return fa[x];
}
}
三、合并连通块
void merge(int a,int b) {
fa[find(a)] = find(b);
d[find(a)] = distance; //预先处理d[]
}
模型应用
并查集不都是树形的嘛
这道题
首先我们钦定一个根节点
跟zhq&wyz大佬学的“钦定”一词orz
然后之后的点如果与之有捕食关系的话就把它们两点merge起来
因为我们维护了每个点i到根节点的距离d[i]
所以容易看出
if(d[i]%3==1) 那它吃
else if(d[i]%3==2) 那它被点吃
else 它与根节点同类
那任意两个点之间的关系
我们就可以通过类似于前缀和的思想
通过(d[x]-d[y])%3来判断
完整CODE
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 5e4+5;
int n,k,lies;
int fa[N], d[N];
void init() {
for(register int i=1; i<=n; i++)
fa[i] = i, d[i] = 0;
}
int find(int x) {
if(fa[x]==x) return x;
else {
int last = fa[x];
fa[x] = find(fa[x]);
d[x] += d[last];
return fa[x];
}
}
int main() {
read(n),read(k);
init();
while(k--) {
int t,x,y;
read(t),read(x),read(y);
if(x>n || y>n) lies++;
else {
int fx = find(x);
int fy = find(y);//找祖源是个递归的过程,应该尽量减少调用
if(t==1) {
if(fx==fy && (d[x]-d[y])%3!=0) lies++;
else if(fx!=fy) {//merge
fa[fx] = fy;
d[fx] = d[y]-d[x];
/*这个人说x和y是同类,我们现在要把这个已知条件加进去
设x到根节点距离是dist,那么(d[x]+dist-d[y])%3应该等于0
然后我们解出来dist应该是 d[y]-d[x](同余方程qwq)
*/
}
} else {
if(fx==fy && (d[x]-d[y]-1)%3) lies++;
else if(fx!=fy) {//merge
fa[fx] = fy;
d[fx] = d[y]-d[x]+1;//同理
}
}
}
}
printf("%d\n",lies);
return 0;
}