相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4195
解题报告
用并查集将相同的变量缩起来
然后判有没有两个不等的变量在一个连通分量即可
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = 300009; int n, fa[N], cet[M], val[N], dif[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int find(int x) { return fa[x] == x? x: fa[x] = find(fa[x]); } int main() { freopen("prog.in", "r", stdin); freopen("prog.out", "w", stdout); for (int T = read(); T; T--) { n = read(); int tot = 0, cnt = 0, tt = 0; for (int i = 1; i <= n; i++) { cet[++tot] = val[++cnt] = read(); cet[++tot] = val[++cnt] = read(); cet[++tot] = read(); } sort(val + 1, val + 1 + cnt); cnt = unique(val + 1, val + 1 + cnt) - val - 1; for (int i = 1; i <= cnt; i++) { fa[i] = i; } for (int i = 1; i <= n; i++) { int t = cet[tot--]; int u = cet[tot--], v = cet[tot--]; u = lower_bound(val + 1, val + 1 + cnt, u) - val; v = lower_bound(val + 1, val + 1 + cnt, v) - val; if (t == 1) { fa[find(u)] = find(v); } else { dif[++tt] = u; dif[++tt] = v; } } bool ok = 1; for (int i = 1; i <= tt; i += 2) { int u = dif[i], v = dif[i + 1]; if (find(u) == find(v)) { ok = 0; break; } } puts(ok? "YES": "NO"); } return 0; }