1 条题解
-
0
/* ID: Keqi Zhao TASK: test LANG: C++ */ #include <iostream> #include <cstdio> #include <algorithm> #define Maxn 1000010 using namespace std; int n, bt, ct, T, b[Maxn * 2], c[Maxn * 2], fa[Maxn * 2]; struct node{ int x, y, z; }a[Maxn]; int find (int x){ if(fa[x] == x) return x; return fa[x] = find(fa[x]); } void merge(int x, int y){ x = find(x); y = find(y); if(x != y) fa[x] = y; } int main() { cin >> T; while(T--){ cin >> n; bt = 0, ct = 0; for(int i = 1; i <= n; i ++){ cin >> a[i].x >> a[i].y >> a[i].z; b[++bt] = a[i].x; b[++bt] = a[i].y; } sort(b + 1, b + bt + 1); for(int i = 1; i <= bt; i++) if(b[i] != b[i - 1]) c[++ct] = b[i]; for(int i = 1; i <= bt; i++){ a[i].x = lower_bound(c + 1, c + ct + 1, a[i].x) - c; a[i].y = lower_bound(c + 1, c + ct + 1, a[i].y) - c; } for(int i = 1; i <= ct; i++) fa[i] = i; for(int i = 1; i <= n; i++) if(a[i].z) merge(a[i].x , a[i].y); bool flag = true; for(int i = 1; i <= n; i++) if(!a[i].z) if(find(a[i].x) == find(a[i].y)){ flag = false; break; } cout << (flag ? "YES" : "NO") << endl; } return 0; }
- 1
信息
- ID
- 127
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 7
- 已通过
- 4
- 上传者