link

#include <bits/stdc++.h>
using namespace std;

unordered_map <int, int> mp;

const int N = 2e5 + 10;
struct node
{
	int x;
	int y;
	int op;
}a[N];
int T, f[N * 2], idx = 0, n;

int cal(int x) 
{
    if (mp.count(x))
	{
		return mp[x];
	}
    return mp[x] = idx ++;
}

int find(int x)
{
	if (f[x] != x) return f[x] = find(f[x]);
	return f[x];
}

int main()
{
	scanf("%d", &T);
	while (T --)
	{
		idx = 0;
		mp.clear();
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++) f[i] = i;
		for (int i = 1; i <= n; i ++)
		{
			scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].op);
			a[i].x = cal(a[i].x), a[i].y = cal(a[i].y);
			if (a[i].op)
			{
				f[find(a[i].x)] = find(a[i].y);
			}
		}
		bool flag = true;
		for (int i = 1; i <= n; i ++)
		{
			if (!a[i].op)
			{
				if (f[find(a[i].x)] == f[find(a[i].y)])
				{
					flag = false;
					break;
				}
			}
		}
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

是一道并查集，找不出错误

错误数据：

10
1
1 2 1
1
2 2 0
10
1 2 1
2 3 1
3 5 1
5 10 1
10 100 1
10000 100 1
1 9999 0
3 2 1
10000 1 0
2 3 1
4
1 7 1
9 7 0
13 9 1
1 13 1
5
7 9 0
9 7 0
3 5 0
1 7 0
2 4 0
9
24 234 1
2837 1 1
235 877 1
242 78 0
23 1 1
223 977 0
254 76 1
235 987 0
877 987 1
9
24 234 1
2837 1 1
242 78 0
23 1 1
223 977 0
254 76 1
235 877 0
235 987 0
877 987 0
4
8 2 0
2 9 1
2 7 1
9 7 0
2
1 1 1
2 2 1
3
9 2 0
1 3 1
2 3 1

正确输出：

YES
NO
NO
NO
YES
NO
YES
NO
YES
YES