【UOJ #14】【UER #1】DZY Loves Graph

http://uoj.ac/problem/14

题解很好的~

不带路径压缩的并查集能保留树的原本形态。

按秩合并并查集可以不用路径压缩,但是因为此题要删除,如果把深度当为秩的话不好更新秩的值,所以把子树大小当为秩。

合并直接合并,删除直接删除,每条边只会被添加进树一次,至多被删除一次。

离线特殊考虑一下return的情况就可以了QwQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 300003;
const int M = 500003;
int in() {
int k = 0; char c = getchar();
for(; c < '0' || c > '9'; c = getchar());
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - 48;
return k;
} int fa[N], sz[N], q[M], tail = 0, intree[M], n, m, cnt = 0; ll ans[M], treesum = 0; int find(int x) {return fa[x] == x ? x : find(fa[x]);} void merge(int x, int y, int len) {
x = find(x); y = find(y);
q[++tail] = len; if (x == y)
intree[len] = -1;
else {
++cnt;
treesum += (ll) len;
if (sz[x] > sz[y]) swap(x, y);
intree[len] = x;
fa[x] = y;
sz[y] += sz[x];
while (fa[y] != y) {
y = fa[y];
sz[y] += sz[x];
}
}
} void del() {
int x = q[tail--];
if (intree[x] == -1) return; --cnt;
treesum -= x;
x = intree[x]; int y = fa[x];
sz[y] -= sz[x];
while (fa[y] != y) {
y = fa[y];
sz[y] -= sz[x];
}
fa[x] = x;
} char c[20];
struct node {
char op;
int x, y;
} Q[M]; int main() {
n = in(); m = in();
for(int i = 1; i <= m; ++i) {
scanf("%s", c);
if ((Q[i].op = c[0]) == 'R') continue;
Q[i].x = in();
if (c[0] == 'A')
Q[i].y = in();
} for(int i = 1; i <= n; ++i)
fa[i] = i, sz[i] = 1; for(int i = 1; i <= m; ++i) {
switch (Q[i].op) {
case 'A':
merge(Q[i].x, Q[i].y, i);
printf("%lld\n", ans[tail] = cnt < n - 1 ? 0 : treesum);
break;
case 'D':
if (Q[i + 1].op == 'R') {
printf("%lld\n", ans[tail - Q[i].x]);
printf("%lld\n", ans[tail]);
} else {
for(int j = 1; j <= Q[i].x; ++j)
del();
printf("%lld\n", ans[tail]);
}
break;
case 'R':
if (Q[i - 1].op == 'A') {
del();
printf("%lld\n", ans[tail]);
}
break;
}
} return 0;
}
上一篇:PE Checksum Algorithm的较简实现


下一篇:mac中显示隐藏文件和.开头的文件