AcWing 240. 食物链
原题链接
中等
作者:
阿飞被注册了
,
2021-06-14 17:27:00
,
所有人可见
,
阅读 215
并查集,链表要记得 初始化!初始化!!初始化!!!
题解在代码里面了
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 10;
//d[N]:记录每个点与父节点的距离 因为是三个物种构成的食物闭环(所以在mod3意义下):距离为1的吃距离为0的;距离为2吃距离为1的;距离为0的吃距离为2的。
int ans = 0, p[N], d[N];
//在路径压缩的时候d[x]更新为x到根节点的距离
int find(int x)
{
if(p[x] != x)
{
//最终回溯时 t 是根节点
int t = find(p[x]);
//这里p[x] 还是 x 的父节点
d[x] += d[p[x]];
//而这里 p[x] 变为 根节点从而实现路径压缩
p[x] = t;
//若row-18 与 row-20 换一下位置即:
// p[x] = t; d[x] += d[p[x];
//那么 p[x] 先变成了 根节点,后面加的时候 就是d[x] + d[根节点] 而d[根节点]==0 所以就加了个寂寞
}
return p[x];
}
int main()
{
int n, m;
cin >> n >> m;
//并查集 记住初始化!!
for(int i = 1; i <= n; i++) p[i] = i;
int x, a, b;
while(m--)
{
cin >> x >> a >> b;
if(a > n || b > n) ans++;
else
{
//pa为a的根节点,pb为b的根节点
int pa = find(a), pb = find(b);
//判断是否是同类
if(x == 1)
{
//pa == pb:a,b在同一棵树上;d[a]-d[b]%3 != 0:意味着这两个点不是同类
if(pa == pb && (d[a] - d[b]) % 3) ans++;
//当这两个点不在同一棵树上
else if(pa != pb)
{
//将根节点pb作为pa的父节点
p[pa] = pb;
//而此时pa到pb的距离a[pa]要满足((d[a]+d[pa]-d[b]) % 3 == 0)
d[pa] = d[b] - d[a];
}
}
//判断是否是a 吃 b 即:b是否是a的父节点
else
{
//若两者在一棵树时且a吃b时必满足(吃比被吃在mod 3时是大一的): (d[a] - d[b] - 1) % 3 == 0.
if(pa == pb && (d[a] - d[b] - 1) % 3) ans++;
//若两者不在同一棵树时
else if (pa != pb)
{
//将pb作为pa父节点
p[pa] = pb;
//那么d[pa]应满足:(d[a] + d[pa] - p[b] - 1) % 3 == 0
d[pa] = 1 + d[b] - d[a];
}
}
}
}
cout << ans;
return 0;
}