题目链接：http://codeforces.com/contest/292/problem/D 给一个无向图，每次删除一些边，求它的连通分量。这道题第一眼看上去想到的就是并查集，不过并不是那么容易能想出来正解，因为如果使用一个裸的并查集必然会超时，所以说记录下来两个数组，一个数组记录的是从前往后找使任意某两个不连通的点连通的第一条边，另一个数组记录的就是从后往前找使任意两个不连通的点连通的第一条边，然后对于k次实验，每次实验都只需要扫描两个数组，从前往后找的数组只要那条边的序号小于l且使两个不连通的点连通了那就连通了，同理，从后往前找的数组大于r且使两个不连通的点连通了也就连通了，都合并完以后直接求连通分量即可。
  view code
1 #include <cstdio>
2 #include <cstring>
3 int p[510], ll[10010], rr[10010];
4 int a[10010], ac;
5 int b[10010], bc;
6 int find(int x){
7 return p[x] != x ? p[x] = find(p[x]) : x;
8 }
9 bool marge(int x, int y){
10 x = find(x); y = find(y);
11 if (x == y) return 0;
12 p[y] = x;
13 return 1;
14 }
15 int main(){
16 memset(a, 0, sizeof(a));
17 memset(b, 0, sizeof(b));
18 ac = 0, bc = 0;
19 int n, m, k;
20 scanf("%d%d", &n, &m);
21 for (int i = 1; i <= m; i++) scanf("%d%d", &ll[i], &rr[i]);
22 for (int i = 1; i <= n; i++) p[i] = i;
23 for (int i = 1; i <= m; i++)
24 if (marge(ll[i], rr[i])) a[ac++] = i;
25 for (int i = 1; i <= n; i++) p[i] = i;
26 for (int i = m; i > 0; i--)
27 if (marge(ll[i], rr[i])) b[bc++] = i;
28 scanf("%d", &k);
29 while (k--){
30 for (int i = 1; i <= n; i++) p[i] = i;
31 int z = n, l, r;
32 scanf("%d%d", &l, &r);
33 for (int i = 0; i < ac; i++)
34 if (a[i] < l)
35 if (marge(ll[a[i]], rr[a[i]])) z -= 1;
36 for (int i = 0; i < bc; i++)
37 if (b[i] > r)
38 if (marge(ll[b[i]], rr[b[i]])) z -= 1;
39 printf("%d\n", z);
40 }
41 return 0;
42 }
43
|