題目鏈接：http://codeforces.com/contest/292/problem/D 給一個無向圖，每次刪除一些邊，求它的連通分量。這道題第一眼看上去想到的就是并查集，不過并不是那么容易能想出來正解，因為如果使用一個裸的并查集必然會超時，所以說記錄下來兩個數(shù)組，一個數(shù)組記錄的是從前往后找使任意某兩個不連通的點連通的第一條邊，另一個數(shù)組記錄的就是從后往前找使任意兩個不連通的點連通的第一條邊，然后對于k次實驗，每次實驗都只需要掃描兩個數(shù)組，從前往后找的數(shù)組只要那條邊的序號小于l且使兩個不連通的點連通了那就連通了，同理，從后往前找的數(shù)組大于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
|