77 lines
2.3 KiB
C++
77 lines
2.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 50010;
|
||
const int M = 3;
|
||
//带权并查集
|
||
/**
|
||
* 并查集：
|
||
* 维护额外信息，本题维护的是每个节点到父节点的距离
|
||
* 并查集中每个集合是树的形式
|
||
* 不管是同类，还是吃的关系，我们都把它们放到同一个集合中去。它们之间的关系用距离描述。
|
||
* 通过上面的记录关系，我们就可以推理出任何两个节点的关系。
|
||
*/
|
||
int n, m;
|
||
int p[N]; //父亲是谁
|
||
int d[N]; //i结点到父结点的距离
|
||
int res; //假话的个数
|
||
|
||
/**
|
||
* p是指节点i的父节点是谁
|
||
* d是指节点i到自己父亲的距离
|
||
* d[x]=1 : x吃根结点
|
||
* d[x]=2 : x被根结点吃
|
||
* d[x]=0 : x与根结点是同类
|
||
* @param x
|
||
* @return
|
||
*/
|
||
int find(int x) {
|
||
if (p[x] != x) {
|
||
int t = find(p[x]);
|
||
d[x] = (d[p[x]] + d[x]) % M;
|
||
p[x] = t;
|
||
}
|
||
return p[x];
|
||
}
|
||
|
||
int main() {
|
||
cin >> n >> m;
|
||
for (int i = 1; i <= n; i++) p[i] = i; //并查集初始化
|
||
//m个条件
|
||
while (m--) {
|
||
int t, x, y;
|
||
cin >> t >> x >> y;
|
||
//如果出现x,y的序号，大于最大号，那么肯定是有问题，是假话
|
||
if (x > n || y > n) {
|
||
res++;
|
||
continue;
|
||
}
|
||
//找出祖先
|
||
int px = find(x), py = find(y);
|
||
//t==1,同类
|
||
if (t == 1) {
|
||
//同一个家族，而且距离值差模3不等于0，表示不是同类,结果值++
|
||
if (px == py && (d[x] - d[y] + M) % M) res++;
|
||
//如果不是同一个家族，需要合并并查集
|
||
if (px != py) {
|
||
p[px] = py;//将px认py为祖先
|
||
d[px] = (d[y] - d[x] + M) % M; //修改路径长度
|
||
}
|
||
}
|
||
//t==2,表示X吃Y
|
||
if (t == 2) {
|
||
//同一个家族,但距离并不是1,那就是错误答案
|
||
if (px == py && (d[x] - d[y] + M) % M != 1) res++;
|
||
//不在同一个家族内，描述刚录入进来的信息，肯定是真话，记录这个信息
|
||
if (px != py) {
|
||
p[px] = py;//将px认py为祖先
|
||
d[px] = (d[y] + 1 - d[x] + M) % M;//修改路径长度
|
||
}
|
||
}
|
||
}
|
||
//输出大吉
|
||
printf("%d\n", res);
|
||
return 0;
|
||
}
|