[数据结构与算法]并查集（扩展域并查集）

/***********
Author Smile
扩展域并查集
处理并查集中的复杂关联问题
注：其中的关系需要根据题目自己拟定
分析题目的状态，每一步的执行情况，开始想代码
注：如果自认为不会超时请试试scanf, printf, 或许这就是转机 
https://vjudge.csgrandeur.cn/contest/476820#problem/G
***********/
#include <iostream>

using namespace std;
const int N = 2e6 + 10;
int n, k;
int fa[N];
int xself, xeat, xen, yself, yeat, yen;
int ans = 0;

void Init()
{
	for (int i = 1; i <= 3 * n; ++i)
		fa[i] = i;
}

int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
	fa[find(x)] = find(y);
}

int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0), cout.tie(0);
	//cin >> n >> k;
	scanf("%d %d", &n, &k);
	Init();
	int d, x, y;
	for (int i = 1; i <= k; ++i)
	{
		// cin >> d >> x >> y;
		scanf("%d %d %d", &d, &x, &y);
		xself = x, xeat = n + x, xen = 2 * n + x;
		yself = y, yeat = n + y, yen = 2 * n + y;
		if (x > n || y > n)
		{
			ans++;
			continue;
		}
		if (d == 1)
		{
			if (find(xeat) == find(yself) || find(yeat) == find(xself))
			{
				ans++;
				continue;
			}
			else 
			{
				merge(xself, yself);
				merge(xeat, yeat);
				merge(xen, yen);
			}
		}
		if (d == 2)
		{
			if (find(xself) == find(yself) || find(yeat) == find(xself))
			{
				ans++;
				continue;
			}
			else 
			{
				merge(xeat, yself);
				merge(xen, yeat);
				merge(xself, yen);
			}
		}
	}
	// cout << ans << endl;
	printf("%d\n", ans);
	return 0;
}