[INFOR] 11皮卡丘打排球

題目連結：https://oj.infor.org/problems/11
　　用dsu去維護關係即可。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,k;
int fa[1500009];
int sz[1500009];
inline void init()
{
    for(int i = 0; i <= 3*n; i++) 
    {
        fa[i] = i;
        sz[i] = 1;
    }
}
inline int find(int x)
{
    return (fa[x]==x)?(fa[x]):(fa[x] = find(fa[x]));
}
inline bool same(int x,int y)
{
    return (find(x) == find(y));
}
inline void unite(int x,int y)
{
    if(same(x,y)) return;
    if(sz[find(x)] < sz[find(y)]) swap(x,y);
    fa[find(y)] = find(x);
    sz[find(x)] += sz[find(y)];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    int ans = 0;
    init();
    while(k--)
    {
        int d,x,y;
        cin >> d >> x >> y;
        if(x > n || y > n)
        {
            ans++;
            continue;
        }
        if(d == 1)
        {
            if(same(x,y+n) || same(x,y+2*n))
            {
                ans++;
                continue;
            } 
            unite(x,y);
            unite(x+n,y+n);
            unite(x+2*n,y+2*n);
        }
        else
        {
            if(same(x,y) || same(x,y+2*n) || x == y)
            {
                ans++;
                continue;
            }
            unite(x,y+n);
            unite(x+n,y+2*n);
            unite(x+2*n,y);
        }
    }
    cout << ans << endl;
}