传送门
思维！重要的是思维！
题目让删边，然而并查集不好删边（并！查！集！啊）
我们离线处理，从后往前添边，这样并查集就可以用了。
用并查集维护连通块个数即可。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 001 5 6 int n, m, k, ans, cnt; 7 int head[N], to[N << 1], next[N << 1], f[N], a[N], anslist[N]; 8 bool vis[N]; 9 10 inline int read() 11 18 19 inline void add(int x, int y) 20 25 26 inline int find(int x) 27 30 31 int main() 32 44 k = read(); 45 for(i = 1; i <= k; i++) 46 50 ans = n k; 51 for(i = 0; i < n; i++) f[i] = i; 52 for(x = 0; x < n; x++) 53 } 64 anslist[k] = ans; 65 for(i = k; i >= 1; i) 66 77 vis[x] = 0; 78 anslist[i 1] = ans; 79 } 80 for(i = 0; i <= k; i++) printf("%d\n", anslist[i]); 81 return 0; 82 }View Code
总结：有些需要删边询问连通性之类的题目，可以试试从后往前用并查集添边。
逆向思维很重要！正着不方便就反着来。
上一篇：[luoguP2754] 星际转移问题（最大流）
下一篇：[luoguP2024] 食物链（并查集）
并查集
