题解

时间刺客

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 3 * 50000 + 10;
// parent[i]：并查集父节点
vector<int> parent(MAX_SIZE);
// rank_：并查集按秩合并使用
vector<int> rank_(MAX_SIZE, 0);
// 并查集查找（带路径压缩）
int find(int x){
    if(parent[x] != x){
        parent[x] = find(parent[x]);
    }
    return parent[x];
}
// 并查集合并
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rank_[x] < rank_[y]) parent[x] = y;
    else{
        parent[y] = x;
        if(rank_[x] == rank_[y]) rank_[x]++;
    }
}
// 初始化并查集
void init(int size){
    for(int i = 1; i <= size; ++i){
        parent[i] = i;
        rank_[i] = 0;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    // 开 3*n 大小空间
    init(3 * n);
    int sum = 0; // 假话数量
    for(int i = 0; i < k; ++i){
        int d, x, y;
        cin >> d >> x >> y;
        // 越界是假话
        if(x > n || y > n){
            sum++;
            continue;
        }
        // 2 X X（自己吃自己）是假话
        if(d == 2 && x == y){
            sum++;
            continue;
        }
        if(d == 1){ // x 和 y 同类
            // 若 x 与 y+n 或 y 与 x+n 属于同一集合，则矛盾
            if(find(x) == find(y+n) || find(y) == find(x+n)){
                sum++;
            }
            else{
                // 合并三类关系
                unite(x, y);
                unite(x+n, y+n);
                unite(x+2*n, y+2*n);
            }
        }
        else{ // d == 2: x 吃 y
            // 若 x 与 y 同类 或 y 吃 x（y 与 x+n 同属一类）则矛盾
            if(find(x) == find(y) || find(y) == find(x+n)){
                sum++;
            }
            else{
                unite(x, y+n);
                unite(x+n, y+2*n);
                unite(x+2*n, y);
            }
        }
    }
    cout << sum << endl;
    return 0;
}