[JSOI2008]星球大战

正向进行很显然很BT, 所以逆向离线此题是个不错的选择. 使用并查集统计劫难之后的联通状态, 然后逐个添加结点即可.
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <vector>
 5 using std::vector;
 6 #define VERTEXMAX 400003
 7 int set[VERTEXMAX], Des[VERTEXMAX], output[VERTEXMAX];
 8 bool Vertex[VERTEXMAX];
 9 vector<int> To[VERTEXMAX];
10 void Initialize()
11 {
12     memset(Vertex, true, sizeof(Vertex));
13     for (int i = 0; i < VERTEXMAX; ++i)
14         set[i] = i;
15 }
16 int Father(int x)
17 {
18     if (set[x] == x)
19         return x;
20     return set[x] = Father(set[x]);
21 }
22 void Union(int x, int y, int &sum)
23 {
24     int a_Father = Father(x);
25     int b_Father = Father(y);
26     if (a_Father != b_Father)
27     {
28         set[a_Father] = b_Father;
29         --sum;
30     }
31 }
32 int main()
33 {
34     Initialize();
35     int V, E, Dn, Block, p = 0;
36     scanf("%d %d", &V, &E);
37     for (int i = 0, x, y; i < E; To[x].push_back(y), To[y].push_back(x), ++i)
38         scanf("%d %d", &x, &y);
39     scanf("%d", &Dn);
40     p = Dn;
41     for (int i = 0; i < Dn; Vertex[Des[i]] = false, ++i)
42         scanf("%d", &Des[i]);
43     Block = V - Dn;
44     for (int i = 0, j; i < V; ++i)
45         if (Vertex[i])
46             for (j = 0; j < To[i].size(); ++j)
47                 if (Vertex[To[i][j]])
48                     Union(i, To[i][j], Block);
49     output[p--] = Block;
50     for (int i = Dn - 1, j, current_star; i > -1; --i)
51     {
52         current_star = Des[i];
53         Vertex[current_star] = true;
54         ++Block;
55         for (j = 0; j < To[current_star].size(); ++j)
56             if (Vertex[To[current_star][j]])
57                 Union(current_star, To[current_star][j], Block);
58         output[p--] = Block;
59     }
60     for (int i = 0; i <= Dn; ++i)
61         printf("%d
", output[i]);
62     return 0;
63 }