【并查集】bzoj1015 - cool's Blog
【并查集】bzoj1015
cool
posted @ 2015年10月07日 19:44
in 数据结构
, 401 阅读
每次删边显然十分复杂，所谓正难则反（= = 数学思路？）
只要把摧毁的建筑倒着加入并查集就行了
每次合并，连通块就会减1，但总的连通块要减去那些还未加入的星球（= = 貌似说不清楚）
直接上代码。
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 | #include <cstdio>#define maxm 200001#define maxn 400001int b[maxn],f[maxn],d[maxn],c[maxn],h[maxn],last[maxn],head[maxn],l;void add(int x,int y){ l++; h[l] = y; last[l] = head[x]; head[x] = l;}int find(int x){ if (f[x] == x) return x; return f[x] = find(f[x]);}void read(int &i){ char x; for (x = getchar();x < '0';x = getchar()); for (i = 0;x >= '0';x = getchar()) i = i * 10 + x - '0';}int main(){ int n,m; scanf("%d%d",&n,&m); for (int i = 1;i <= m;i++) { int x,y; read(x);read(y); add(++x,++y); add(y,x); } int q; read(q); for (int i = 1;i <= n;i++) b[i] = 1,f[i] = i; for (int i = 1;i <= q;i++) { read(d[i]); b[++d[i]] = 0; } int t = q;\\t就是还没加入的星球个数 int sum = n; for (int i = 1;i <= n;i++) if (b[i] == 1) { for (int x = head[i];x;x = last[x]) if (b[h[x]] == 1) { int r1 = find(i),r2 = find(h[x]); if (r1 != r2) { f[r1] = r2; sum--; } } } for (int i = q;i >= 1;i--) { c[i] = sum - t; b[d[i]] = 1; for (int x = head[d[i]];x;x = last[x]) if (b[h[x]] == 1) { int r1 = find(d[i]),r2 = find(h[x]); if (r1 != r2) { f[r1] = r2; sum--; } } t--; } printf("%d\n",sum-t); for (int i = 1;i <= q;i++) printf("%d\n",c[i]); return 0;} |
评论 (0)