粗略看了一下网上其他题解，都是暴力跑的，也就是对于每个询问重建并查集，这样其实时间复杂度是$O(n^2logn)$的，十分不优秀。
其实有更好的解法，就是时间倒流法，倒序处理每个询问，每个把删去一个点删边改成加上一个点加边，一遍并查集即可。
每次判断是否合并了两个以上的连通块。
注意一条边可用当且仅当两端的点都存在。
1 #include <bits/stdc++.h> 2 #define Mid ((l + r) >> 1) 3 #define lson (rt << 1) 4 #define rson (rt << 1 | 1) 5 using namespace std; 6 int read(){ 7 char c; int num, f = 1; 8 while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; 9 while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; 10 return f * num; 11 } 12 const int N = 509; 13 int n, m, pre[N], a[N], f[N], vis[N]; 14 vector<int> ver[N]; 15 int fid(int x) { 16 return pre[x] == x ? x : (pre[x] = fid(pre[x])); 17 } 18 signed main() 19 { 20 n = read(); m = read(); 21 for(int i = 1; i <= m; i++) { 22 int x = read() + 1, y = read() + 1; 23 ver[x].push_back(y); 24 ver[y].push_back(x); 25 } 26 for(int i = 1; i <= n; i++) pre[i] = i; 27 int q = read(); 28 for(int i = 1; i <= n; i++) vis[i] = 1; 29 for(int i = 1; i <= q; i++) vis[a[i] = read() + 1] = 0; 30 for(int x = 1; x <= n; x++) if(vis[x]) 31 for(auto j : ver[x]) 32 if(vis[j] && fid(j) != fid(x)) 33 pre[fid(j)] = fid(x); 34 for(int i = q; i; i--) { 35 int ff = 0; 36 for(auto j : ver[a[i]]) { 37 if(vis[j] && fid(j) != fid(a[i])) { 38 pre[fid(j)] = fid(a[i]); 39 ff++; 40 } 41 } 42 vis[a[i]] = 1; 43 if(ff > 1) f[i] = 1; 44 } 45 for(int i = 1; i <= q; i++) { 46 if(f[i]) printf("Red Alert: City %d is lost! ", a[i] - 1); 47 else printf("City %d is lost. ", a[i] - 1); 48 } 49 if(q == n) { 50 printf("Game Over. "); 51 } 52 return 0; 53 }