01/22
20:32
传送门:https://www.luogu.org/problem/show?pid=1955
题解一:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1000100; const int mod = 1000000; int n, T, x, y, e, cnt; int ueq[maxn][2], fa[maxn << 1]; inline int getint() { int r = 0, k = 1; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') k = -1; for(; c >= '0' && c <= '9'; c = getchar()) r = r * 10 + c - '0'; return r * k; } inline int hash(int x) { return x > mod ? (mod + x / mod + x % mod): x; } int get_father(int x) { return fa[x] = (fa[x] == x) ? x : get_father(fa[x]); } int main(int argc, char const * argv[]) { T = getint(); while(T--) { cnt = 0; n = getint(); for(int i = 1; i < maxn << 1; i++) fa[i] = i; for(int i = 1; i <= n; i++) { x = getint(); y = getint(); e = getint(); x = hash(x); y = hash(y); if(e == 1) fa[get_father(x)] = get_father(y); else { ++cnt; ueq[cnt][0] = x; ueq[cnt][1] = y; } } bool flag = 1; for(int i = 1; i <= cnt; i++) { if(get_father(ueq[i][0]) == get_father(ueq[i][1])) { flag = 0; break; } } printf(flag ? ("YES\n") : ("NO\n")); } return 0; } |
题解二:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int maxn = 1000010; int n, sz, tp; int tmp[maxn << 1], Hash[maxn << 1], p[maxn << 1]; struct Node { int x, y; bool tp; } s[maxn]; inline int getint() { int r = 0, k = 1; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') k = -1; for(; c >= '0' && c <= '9'; c = getchar()) r = r * 10 + c - '0'; return r * k; } int Find_Hash(int x) { int l = 1, r = tp, mid; while(r - l > 1) { mid = (l + r) >> 1; if(Hash[mid] > x) r = mid; else if(Hash[mid] < x) l = mid; else if(Hash[mid] == x) return mid; } if(Hash[l] == x) return l; return r; } bool cmp(const Node &A, const Node &B) { return A.tp > B.tp; } inline int find(int x) { int r = x, pre; while(p[r] != r) r = p[r]; while(x != r) { pre = p[x]; p[x] = r; x = pre; } return r; } int main(int argc, char const * argv[]) { int T = getint(); int fx, fy; while(T--) { n = getint(); sz = 0; for(int i = 1; i <= n; i++) { s[i].x = getint(); s[i].y = getint(); s[i].tp = getint(); tmp[++sz] = s[i].x; tmp[++sz] = s[i].y; } sort(tmp + 1, tmp + sz + 1); tp = 1; Hash[tp] = tmp[1]; for(int i = 2; i <= sz; i++) { if(tmp[i] != tmp[i - 1]) { Hash[++tp] = tmp[i]; } } sort(s + 1, s + n + 1, cmp); for(int i = 1; i <= tp; i++) p[i] = i; int rec = 0, fool = 0; for(int i = 1; s[i].tp == 1 && i <= n; i++) { fx = find(Find_Hash(s[i].x)); fy = find(Find_Hash(s[i].y)); p[fx] = fy; rec = i; } for(int i = rec + 1; i <= n; i++) { fx = find(Find_Hash(s[i].x)); fy = find(Find_Hash(s[i].y)); if(fx == fy) { fool = 1; puts("NO\n"); break; } } if(!fool) puts("YES\n"); } return 0; } |