題目鏈接：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
|