题目链接

题目

由题意可知， 一共有3种关系， 就开3倍大的数组。

看别人的概念解释（反正我写不来）

概念解释

注意， 种类并查集求的并非种类， 而是关系！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 5;
int f[3 * N];
int tofind(int x){
    if (f[x] != x){
        f[x] = tofind(f[x]);
    }
    return f[x];
}

void tojoin(int x, int y){
    x = tofind(x);
    y = tofind(y);
    if (x != y){
        f[x] = y;
    }
}
int main() {
    /*
     a 吃 b
     a == b + n      a + n == b + 2 * n    a + 2 * n == b
     a 和 b 同类
     a == b     a + n == b + n        a + 2 * n == b + 2 * n
     b 吃 a
     b == a + n     b + n == a + 2 * n      b + 2 * n == a
     */
    int n, k, d, x, y;
    int sum = 0;
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= 3 * n; i++){
        f[i] = i;
    }
    while(k--){
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n){
            sum++;
            continue;
        }
        if (d == 1){
            if (tofind(x) == tofind(y + n) || tofind(x + n) == tofind(y)){
                sum++;
            }
            else{
                tojoin(x, y);
                tojoin(x + n, y + n);
                tojoin(x + n + n, y + n + n);
            }
        }
        else{
            if (tofind(x) == tofind(y) || tofind(y) == tofind(x + n)){
                sum++;
            }
            else{
                tojoin(x, y + n);
                tojoin(x + n, y + n + n);
                tojoin(x + n + n, y);
            }
        }
    }
    cout << sum << "\n";
    return 0;
}