RE求助
查看原帖
RE求助
816204
Light_LE楼主2024/12/21 23:01
#include <bits/stdc++.h>
#define fin cin
#define fout cout

#define maxn 100010
using namespace std;
int n, btop, ctop, T;
struct Edge {
	int x, y, z;
}edge[maxn];
int b[maxn * 2], c[maxn * 2];
int fa[maxn * 2];
int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}
int merge(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) {
		fa[x] = y;
	}
}
int main() {
	//ifstream fin("light.in");
	//ofstream fout("light.out");
	ios::sync_with_stdio(0); fin.tie(0); fout.tie(0);

	fin >> T;
	while (T--) {
		fin >> n;
		btop = 0, ctop = 0;
		for (int i = 1; i <= n; i++) {
			fin >> edge[i].x >> edge[i].y >> edge[i].z;
			b[++btop] = edge[i].x;
			b[++btop] = edge[i].y;
		}
		
		// 离散化 
		sort(b + 1, b + btop + 1);
		for (int i = 1; i <= btop; i++) {// 去重 
			if (b[i] != b[i - 1]) {
				c[++ctop] = b[i];
			}
		}
		for (int i = 1; i <= n; i++) {
			edge[i].x = lower_bound(c + 1, c + ctop + 1, edge[i].x) - c;
			edge[i].y = lower_bound(c + 1, c + ctop + 1, edge[i].y) - c;
		}
		
		// 并查集建立关系 
		for (int i = 1; i <= ctop; i++) {
			fa[i] = i;
		}
		for (int i = 1; i <= n; i++) {
			if (edge[i].z) {
				merge(edge[i].x, edge[i].y);
			}
		}
		bool flag = 1;
		for (int i = 1; i <= n; i++) {
			if (edge[i].z == 0) {
				if (find(edge[i].x) == find(edge[i].y)) {
					flag = 0;
					break;
				}
			}
		}
		
		if (flag) {
			fout << "YES" << endl;
		}
		else {
			fout << "NO" << endl;
		}
	}
	return 0;
}
2024/12/21 23:01
加载中...