#include <iostream>
using namespace std;
static const int MAX = 5000;
static const int INF = (1 << 20);
int par[MAX]; //父亲
int Rank[MAX];
//初始化n 个元素
void initi(int n){
for(int i = 0; i < n; i++){
par[i] = i;
Rank[i] = 0;
}
}
//查询树的根
int Find(int x){
if(par[x] == x) return x;
else return par[x] = Find(par[x]);
}
//合并x 和 y所属的集合
void unite(int x, int y){
x = Find(x);
y = Find(y);
if(x == y) return;
if(Rank[x] < Rank[y]) par[x] = y;
else{
par[y] = x;
if(Rank[x] == Rank[y]) Rank[x]++;
}
}
//判断x 和 y 是否属于同一个集合
bool same(int x, int y){
return Find(x) == Find(y);
}
int N,K;
int T[MAX], X[MAX], Y[MAX];
int main(){
cin >> N >> K;
for(int i = 0; i < K; i++){
cin >> T[i] >> X[i] >> Y[i];
}
//初始化并查集
//元素x, x + N, x + 2 * N 分别代表 x-A, x - B, x - C
initi(3 * N);
int ans = 0; //不正确的信息数目
for(int i = 0; i < K; i++){
int t = T[i];
int x = X[i] - 1, y = Y[i] - 1; //把输入变成0, ...N-1的范围
//不正确的编号
if(x < 0 || x >= N || y < 0 || y >= N){
ans++;
continue;
}
if(t == 1){
//x 和 y 属于同一类的信息
if(same(x, y + N) || same(x, y + 2 * N)) ans++;
else{
unite(x, y);
unite(x + N, y + N);
unite(x + 2 * N, y + 2 * N);
}
}
else{
//x 吃 y 的信息
if(same(x, y) || same(x, y + 2 * N)){
ans++;
}
else{
unite(x, y + N);
unite(x + N, y + 2 * N);
unite(x + 2 * N, y);
}
}
}
cout << ans << endl;
}
8 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复