RE 求助
查看原帖
RE 求助
556110
_Timeless_楼主2023/3/16 22:18
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 5;

int b[N], f[N];

struct node
{
	int x, y, e;
}a[N];

bool cmp(node x, node y)
{
	return x.e > y.e;
}

void init(int x)
{
	for(int i = 1; i <= x; i++)
	{
		f[i] = i;
	}
}

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

int main()
{
	int t;
	bool flag;
	cin >> t;
	while(t--)
	{
		memset(b, 0, sizeof(b));
    	memset(a, 0, sizeof(a));
    	memset(f, 0, sizeof(f));
		int n, tot = 0;
		flag = true;
		cin >> n;
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i].x >> a[i].y >> a[i].e;
			b[++tot] = a[i].x;
			b[++tot] = a[i].y;
		}
		sort(b + 1, b + tot + 1);
		int cnt = unique(b + 1, b + cnt + 1) - b - 1;
		for(int i = 1; i <= n; i++)
		{
			a[i].x = lower_bound(b + 1, b + cnt + 1, a[i].x) - b;
			a[i].y = lower_bound(b + 1, b + n + 1, a[i].y) - b;
		}
		init(cnt);
		sort(a + 1, a + n + 1, cmp);
		for(int i = 1; i <= n; i++)
		{
			int r1 = find(a[i].x);
			int r2 = find(a[i].y);
			if(a[i].e)  f[r1] = r2;
			else
			{
				if(r1 == r2)
				{
					cout << "NO\n";
					flag = false;
					break;
				}
			}
		}
		if(flag)  cout << "YES\n";
	}
	
	
	return 0;
}
2023/3/16 22:18
加载中...