维护联通块自然想到并查集，然而题中说是删边，不是很好做，因此我们可以离线下来然后倒序操作，就变成了添加边的同时维护联通块数量。
首先我们把k次打击后剩的边都添加到图中，表示倒序时的初始状态。然后将 i 从 k 到1枚举，将第 i 个被袭击的星球 del[i] 连的所有边都加入图中，同时维护并查集，当然要满足他连的星球也是未被袭击的用一个bool数组维护即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 2e6 + 5; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) 26 { 27 ans = ans * 10 + ch - '0'; ch = getchar(); 28 } 29 if(last == '-') ans = -ans; 30 return ans; 31 } 32 inline void write(ll x) 33 { 34 if(x < 0) putchar('-'), x = -x; 35 if(x >= 10) write(x / 10); 36 putchar(x % 10 + '0'); 37 } 38 39 int n, m, k; 40 vector v[maxn << 1]; 41 struct Node 42 { 43 int x, y; 44 }t[maxn]; 45 int del[maxn]; 46 bool vis[maxn << 1]; 47 int num; 48 49 int p[maxn << 1]; 50 void init(int n) 51 { 52 for(int i = 1; i <= n; ++i) p[i] = i; 53 } 54 int Find(int x) 55 { 56 return x == p[x] ? x : p[x] = Find(p[x]); 57 } 58 59 int ans[maxn]; 60 61 int main() 62 { 63 n = read(); m = read(); 64 init(n); 65 for(int i = 1; i <= m; ++i) 66 { 67 int x = read(), y = read(); 68 v[x].push_back(y); v[y].push_back(x); 69 } 70 k = read(); 71 for(int i = 1; i <= k; ++i) 72 { 73 del[i] = read(); 74 vis[del[i]] = 1; 75 } 76 num = n - k; 77 for(int i = 1; i <= n; ++i) if(!vis[i]) 78 { 79 for(int j = 0; j < (int)v[i].size(); ++j) 80 { 81 if(!vis[v[i][j]]) 82 { 83 int px = Find(i), py = Find(v[i][j]); 84 if(px != py) {p[px] = py; num--;} //要合并成一个联通块 85 } 86 } 87 } 88 for(int i = k; i > 0; --i) 89 { 90 ans[i] = num; 91 for(int j = 0; j < (int)v[del[i]].size(); ++j) 92 { 93 int e = v[del[i]][j]; 94 if(!vis[e]) 95 { 96 int px = Find(del[i]), py = Find(e); 97 if(px != py) {p[px] = py; num--;} 98 } 99 }100 vis[del[i]] = 0; num++; //别忘了，现在del[i]变成了未被袭击的星球 101 }102 ans[0] = num;103 for(int i = 0; i <= k; ++i) {write(ans[i]); enter;}104 return 0;105 }