AcWing 240. 食物链
原题链接
中等
作者:
黑夜最相似
,
2021-01-20 21:50:32
,
所有人可见
,
阅读 291
p[] -- 存储每个节点的父节点, 用根节点维护一个集合 : p[x] = x, 表示根节点;
d[] -- 开始存储到父节点的距离, 路径压缩后为到根节点的距离
用每个节点到根节点的距离来定义和维护 A, B, C 之间的关系
+++ 0, 表示同类
+
d[x] %3 ++++ 1,表示 x 吃根节点
+
+++ 2,表示被根节点吃
find(x) 在递归回溯的时候, 将所有节点都指向根节点(p[x] = find(p[x)),称为并查集的路径压缩
由于需要进行路径压缩,需要维护当前节点到父节点,即根节点的距离
将当前节点指向根节点之前,需要先记录到父节点的距离 d[x] += d[p[x]]
当前结果作为真话,记录在集合中时,维护到新根节点的距离
d[px] = d[y] - d[x]; 表示为同一类
d[px] = d[y] + 1 - d[x]; 表示吃与被吃关系
C++ 代码
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) p[i] = i;
int res = 0;
while(m--)
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if(x > n || y > n) res++;
else
{
int px = find(x), py = find(y);
if(t == 1)
{
if(px == py && (d[x] - d[y]) % 3) res++;
else if(px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if(px == py && (d[x] - d[y] - 1) % 3) res++;
else if(px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n", res);
}