带权并查集
题意:有三类动物,给出所有的动物都是属于这三类的其中一类,三类动物是成环状互相吃的,给定n个动物和m句话,每句话描述了多个动物之间的关系,同类/吃的关系,按照顺序,找出假话是哪些,最终输出有多少个假话。
假话的条件(满足其中之一就是假话):
- 动物编号不在$1-n$范围内
- x吃x
- 与之前的话冲突
维护一个并查集集合,并且不仅维护之间的关系,更重要的是维护每个点到根节点的距离。
把所有动物都用一个集合来维护,定义:
- $x$点到根节点的距离%3 == 0,则$x$点和根节点是同类且吃为吃根节点%3 == 2的类
- $x$点到根节点的距离%3 == 1,则$x$点吃为吃根节点%3 == 0的类
- $x$点到根节点的距离%3 ==2,则$x$点吃为吃根节点%3 == 1的类
\
- 同类关系:
- 不在一个集合,归并x和y所在的集合
其中归并是将x所在集合的根节点设置为b所在集合根节点,如何设置图中d的距离呢?
要满足:
$(dx + d) \% 3 == dy \% 3$
$d \% 3 == (dy - dx) \% 3$
$d == dy - dx$
- 在一个集合,如何判断是否是同类?
同类要满足:
$dx \% 3 == dy \% 3$
$(dx - dy) \% 3 == 0$
- x吃y关系
- 不在一个集合,归并x和y所在的集合
其中,d如何设置?
要满足:
$(dx + d + 1) \% 3 == dy \% 3$
$d \% 3 == (dy - dx - 1) \% 3$
$d == dy - dx - 1$
- 在一个集合,判断是否成立x吃y的关系?
x吃y要满足:
$dx \% 3 + 1 == dy \% 3$
$(dx - dy + 1) \% 3 == 0$
时间复杂度$O(MC)$,空间复杂度$O(N)$
AC代码
#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N]; //d[x]表示x到根节点的距离
int n, m;
//路径压缩+维护边权
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() {
//读入,初始化并查集
cin >> n >> m;
for (int i = 1 ; i <= n ; i ++) p[i] = i;
int res = 0;
while (m --) {
int c, x, y;
cin >> c >> x >> y;
if (x > n || y > n) res ++; //编号不合法
else if (c == 2 && x == y) res ++; //x吃x
else {
int px = find(x), py = find(y);
if (c == 1) {
//同类关系
if (px != py) {
p[px] = py;
d[px] = d[y] - d[x];
} else if ((d[x] - d[y]) % 3 != 0) res ++;
} else {
//x吃y
if (px != py) {
p[px] = py;
d[px] = d[y] - d[x] - 1;
} else if ((d[x] - d[y] + 1) % 3 != 0) res ++;
}
}
}
//输出答案
cout << res << endl;
return 0;
}