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

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using std::vector; 6 #define VERTEXMAX 400003 7 int set[VERTEXMAX], Des[VERTEXMAX], output[VERTEXMAX]; 8 bool Vertex[VERTEXMAX]; 9 vector
         
           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\n", output[i]);62     return 0;63 }