1. #include <iostream>
  2. using namespace std;
  3. static const int MAX = 5000;
  4. static const int INF = (1 << 20);
  5. int par[MAX]; //父亲
  6. int Rank[MAX];
  7. //初始化n 个元素
  8. void initi(int n){
  9. for(int i = 0; i < n; i++){
  10. par[i] = i;
  11. Rank[i] = 0;
  12. }
  13. }
  14. //查询树的根
  15. int Find(int x){
  16. if(par[x] == x) return x;
  17. else return par[x] = Find(par[x]);
  18. }
  19. //合并x 和 y所属的集合
  20. void unite(int x, int y){
  21. x = Find(x);
  22. y = Find(y);
  23. if(x == y) return;
  24. if(Rank[x] < Rank[y]) par[x] = y;
  25. else{
  26. par[y] = x;
  27. if(Rank[x] == Rank[y]) Rank[x]++;
  28. }
  29. }
  30. //判断x 和 y 是否属于同一个集合
  31. bool same(int x, int y){
  32. return Find(x) == Find(y);
  33. }
  34. int N,K;
  35. int T[MAX], X[MAX], Y[MAX];
  36. int main(){
  37. cin >> N >> K;
  38. for(int i = 0; i < K; i++){
  39. cin >> T[i] >> X[i] >> Y[i];
  40. }
  41. //初始化并查集
  42. //元素x, x + N, x + 2 * N 分别代表 x-A, x - B, x - C
  43. initi(3 * N);
  44. int ans = 0; //不正确的信息数目
  45. for(int i = 0; i < K; i++){
  46. int t = T[i];
  47. int x = X[i] - 1, y = Y[i] - 1; //把输入变成0, ...N-1的范围
  48. //不正确的编号
  49. if(x < 0 || x >= N || y < 0 || y >= N){
  50. ans++;
  51. continue;
  52. }
  53. if(t == 1){
  54. //x 和 y 属于同一类的信息
  55. if(same(x, y + N) || same(x, y + 2 * N)) ans++;
  56. else{
  57. unite(x, y);
  58. unite(x + N, y + N);
  59. unite(x + 2 * N, y + 2 * N);
  60. }
  61. }
  62. else{
  63. //x 吃 y 的信息
  64. if(same(x, y) || same(x, y + 2 * N)){
  65. ans++;
  66. }
  67. else{
  68. unite(x, y + N);
  69. unite(x + N, y + 2 * N);
  70. unite(x + 2 * N, y);
  71. }
  72. }
  73. }
  74. cout << ans << endl;
  75. }
点赞(0)
 

8 分

1 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论