五十分求助,实在不知道哪错了,求大佬解决。
查看原帖
五十分求助,实在不知道哪错了,求大佬解决。
874676
silentzdw楼主2023/7/30 17:45
#include <bits/stdc++.h>
using namespace std;
const int N = 10000050;
typedef long long ll;
ll p[N];

struct node {
	ll ai;
	ll bi;
	ll op;
} a[N];

bool cmp1(node a, node b) {
	return a.op > b.op;
}

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

int main() {
	int t;
	cin >> t;
	while (t--) {
		memset(p, 0, sizeof(p));
		memset(a, 0, sizeof(a));
		ll n;
		cin >> n;

		for (int i = 1; i <= n; i++) {
			cin >> a[i].ai >> a[i].bi >> a[i].op;
		}
		vector<ll>alls;
		for (int i = 1; i <= n; i ++) {
			alls.push_back(a[i].ai);
			alls.push_back(a[i].bi);
		}
		sort(alls.begin(), alls.end());
		alls.erase(unique(alls.begin(), alls.end()), alls.end());
		for (int i = 1; i <= alls.size(); i++) {
			a[i].ai = lower_bound(alls.begin(), alls.end(), a[i].ai) - alls.begin() + 1;
			a[i].bi = lower_bound(alls.begin(), alls.end(), a[i].bi) - alls.begin() + 1;

		}

		for (int i = 1; i <= alls.size(); i++) {
			p[i] = i;
		}

		int flag = 0;
		sort(a + 1, a + n + 1, cmp1);
		for (int i = 1; i <= n; i++) {
			if (a[i].op == 1) {
				p[find(a[i].ai)] = find(a[i].bi);

			} else if (a[i].op == 0) {

				if (find(a[i].ai) == find(a[i].bi)) {
					cout << "NO" << "\n";
					flag = 1;
					break;
				}
			}

		}
		if (!flag)
			cout << "YES" << "\n";
	}
	return 0;

}
2023/7/30 17:45
加载中...