POJ1182.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long int ll;
const int INF = 100000000;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
struct unionf{
    vector <int> par, rank;
    int root(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = root(par[x]);
        }
    }
    void init(int n){
        rep(i, n){
            par.push_back(i);
            rank.push_back(0);
        }
    }
    void unite(int x, int y){
        x = root(x); y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
};
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    vector <int> t(k), x(k), y(k);
    rep(i, k) scanf("%d%d%d", &t[i], &x[i], &y[i]);
    unionf uni;
    uni.init(n*3);
    int ans = 0;
    rep(i, k){
        int a = x[i] - 1, b = y[i] - 1;
        if(a < 0 || b < 0 || a >= n || b >= n){
            ans++;
            continue;
        }
        if(t[i] == 1){
            if(uni.same(a, b + n) || uni.same(a, b + n * 2)){
                ans++;
            }else{
                rep(j, 3) uni.unite(a + n * j, b + n * j);
            }
        }else{
            if(uni.same(a, b) || uni.same(a, b + n * 2)){
                ans++;
            }else{
                uni.unite(a, b + n);
                uni.unite(a + n, b + n * 2);
                uni.unite(a + n * 2, b);
            }
        }
    }
    printf("%d\n", ans);
}