[JSOI2008]星球大战

正向进行很显然很BT, 所以逆向离线此题是个不错的选择. 使用并查集统计劫难之后的联通状态, 然后逐个添加结点即可.

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #include <vector>

 using std::vector;

 #define VERTEXMAX 400003

 int set[VERTEXMAX], Des[VERTEXMAX], output[VERTEXMAX];

 bool Vertex[VERTEXMAX];

 vector<int> To[VERTEXMAX];

 void Initialize()

 {

     memset(Vertex, true, sizeof(Vertex));

     for (int i = ; i < VERTEXMAX; ++i)

         set[i] = i;

 }

 int Father(int x)

 {

     if (set[x] == x)

         return x;

     return set[x] = Father(set[x]);

 }

 void Union(int x, int y, int &sum)

 {

     int a_Father = Father(x);

     int b_Father = Father(y);

     if (a_Father != b_Father)

     {

         set[a_Father] = b_Father;

         --sum;

     }

 }

 int main()

 {

     Initialize();

     int V, E, Dn, Block, p = ;

     scanf("%d %d", &V, &E);

     for (int i = , x, y; i < E; To[x].push_back(y), To[y].push_back(x), ++i)

         scanf("%d %d", &x, &y);

     scanf("%d", &Dn);

     p = Dn;

     for (int i = ; i < Dn; Vertex[Des[i]] = false, ++i)

         scanf("%d", &Des[i]);

     Block = V - Dn;

     for (int i = , j; i < V; ++i)

         if (Vertex[i])

             for (j = ; j < To[i].size(); ++j)

                 if (Vertex[To[i][j]])

                     Union(i, To[i][j], Block);

     output[p--] = Block;

     for (int i = Dn - , j, current_star; i > -; --i)

     {

         current_star = Des[i];

         Vertex[current_star] = true;

         ++Block;

         for (j = ; j < To[current_star].size(); ++j)

             if (Vertex[To[current_star][j]])

                 Union(current_star, To[current_star][j], Block);

         output[p--] = Block;

     }

     for (int i = ; i <= Dn; ++i)

         printf("%d\n", output[i]);

     return ;

 }