51nod1515 明辨是非 并查集 + set-LMLPHP

一开始想的时候,好像两个并查集就可以做......然后突然懂了什么....

相同的并查集没有问题,不同的就不能并查集了,暴力的来个set就行了.....

合并的时候启发式合并即可做到$O(n \log^2 n)$

如果打$splay$,那么启发式合并可以做到$O(n \log n)$

#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; extern inline char gc() {
static char RR[], *S = RR + , *T = RR + ;
if(S == T) fread(RR, , , stdin), S = RR;
return *S ++;
}
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
} #define pc(o) *O ++ = o
char WR[], *O = WR;
inline void write(int opt) {
if(opt == ) pc('Y'), pc('E'), pc('S'), pc('\n');
else pc('N'), pc('O'), pc('\n');
} #define ri register int
#define sid 200050 set <int> f[sid];
int T[sid], n, tot;
int x[sid], y[sid], p[sid], fa[sid]; inline int find(int o) {
if(fa[o] == o) return o;
return fa[o] = find(fa[o]);
} int main() {
n = read();
for(ri i = ; i <= n; i ++) {
x[i] = read(); y[i] = read(); p[i] = read();
T[++ tot] = x[i]; T[++ tot] = y[i];
}
sort(T + , T + tot + );
tot = unique(T + , T + tot + ) - T - ;
for(ri i = ; i <= n; i ++) {
x[i] = lower_bound(T + , T + tot + , x[i]) - T;
y[i] = lower_bound(T + , T + tot + , y[i]) - T;
}
for(ri i = ; i <= tot; i ++) fa[i] = i;
for(ri i = ; i <= n; i ++) {
int u = find(x[i]), v = find(y[i]);
if(!p[i]) {
if(u == v) write(-);
else write(), f[u].insert(v), f[v].insert(u);
}
else {
if(u == v) write();
else if(f[u].count(v)) write(-);
else {
write();
if(f[u].size() > f[v].size()) swap(u, v); fa[u] = v;
for(set <int> :: iterator it = f[u].begin(); it != f[u].end(); it ++)
{ int w = *it; f[w].insert(v); f[v].insert(w); }
}
}
}
fwrite(WR, , O - WR, stdout);
return ;
}
05-27 14:45