[luoguP1197] [JSOI2008]星球大战（并查集）

传送门

思维！重要的是思维！

题目让删边，然而并查集不好删边（并！查！集！啊）

我们离线处理，从后往前添边，这样并查集就可以用了。

用并查集维护连通块个数即可。

——代码

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

总结：有些需要删边询问连通性之类的题目，可以试试从后往前用并查集添边。

　　　逆向思维很重要！正着不方便就反着来。

上一篇：[luoguP2045] 方格取数加强版（最小费用最大流）

下一篇：[luoguP2486] [SDOI2011]染色（树链剖分）

---

并查集