HAUT 1285: 军团再临【并查集*逆向思维】

1285: 军团再临

时间限制: 1 秒   内存限制: 128 MB 提交: 56   解决: 20 提交  状态 

题目描述

燃烧军团大举入侵艾泽拉斯，现以在艾星建立了大量的军事要塞，这些要塞通过若干个道路直接或间接连接。如果两个城市是连通的，那么它们处于同一连通块之中。现在抗魔联军发明了一种威力巨大的法术，每发动一次将会直接摧毁一个军事要塞，同时也摧毁与他相连的道路。每进行一次打击，联军需要知道未被摧毁的要塞的连通块数。联军会给出最初要塞的连通情况以及打击顺序，请快速计算每次打击之后未被摧毁的要塞的连通块数量。

输入

输入第一行为两个整数n,m分别表示要塞个数和道路个数。1<=n<=100000,1<=m<=200000。 接下来m行每行两个整数x,y (1<=x,y<=n)表示要塞x和要塞y之间有一条道路连接。 接下来一行为一个整数k表示将会打击的要塞数量。1<=k<=n。 接下来k行每行一个整数v表示会打击的城市这k个数互不相同,1<=v<=n。

输出

第一行输出最初的连通块个数，后k行一次输出每次打击后的结果。

样例输入

8 13 1 2 2 7 7 6 6 1 1 7 2 3 3 4 4 5 5 6 8 2 8 3 8 7 4 7 5 2 7 4 6 8

样例输出

1 1 1 2 3 3

提示

来源

提交  状态 

思路：（标程，有所改动）

这道题考察并查集的逆向思维，先不一一求联通块，先删点和边，最后再用并查集依次逆着加上这些边和点，很好的题目；

/* 按顺序拆点是不好处理的，但是我们可以记录拆点的顺序然后倒过来加点。 每次加点通过并查集来判断连通块数量并记录答案，然后按顺序输出 就行了。先计算拆完点后的连通块数，每次加点将该点和与之相连且 未拆掉的点并入一个集合并判断连通块数。 */ #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int maxm = 400005; int pre[maxm], a[maxm], flag[maxm] = { 0 }; int sum[maxm] = { 0 }, vis[maxm] = { 0 }; vector<int>v[maxm]; int find(int k) { if (pre[k] == k) return k; return pre[k] = find(pre[k]); } int main() { int n, i, j, k, m, x, y; scanf("%d%d", &n, &m); for (i = ; i <= n; i++) pre[i] = i; for (i = 1; i <= m; i++) { scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); } scanf("%d", &k); for (i = 0; i < k; i++) { scanf("%d", &a[i]); flag[a[i]] = 1; } int t1, t2; for (i = 1; i <= n; i++) { //逆着加边，这是最后剩下的所有边，构建图 if (flag[i]) continue; for (j = 0; j < v[i].size(); j++) { if (flag[v[i][j]]) continue; t1 = find(i), t2 = find(v[i][j]); if (t1 != t2) pre[t1] = t2; } } for (i = 1; i <= n; i++) { //最后剩下的连通块 if (flag[i]) continue; int xx = find(i); if (!vis[xx]) { sum[k]++; vis[xx] = 1; } } int rev; for (i = k - 1; i >= 0; i--) { flag[a[i]] = 0; sum[i] = sum[i + 1]; rev = 0; for (j = 0; j < v[a[i]].size(); j++) { if (flag[v[a[i]][j]]) continue; rev++; t1 = find(a[i]), t2 = find(v[a[i]][j]); if (t1 != t2) { if (t1 != a[i]) sum[i]--; pre[t1] = t2; } } if (rev == 0) sum[i]++; } for (i = 0;i <= k;i++) printf("%d\n", sum[i]); return 0; }我来粘一发TLE代码（ 果然是菜，想蹭弱数据，没想到逆向思维）：

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #define max_n 400010 using namespace std; int cnt, n, m, k, v, res; int head[max_n], vis[max_n], gg[max_n]; bool flag = true; struct node { int to; int next; }edge[max_n]; void addedge(int u, int w) { edge[cnt].to = w; edge[cnt].next = head[u]; head[u] = cnt++; } void bfs(int x) { if(!flag) gg[x] = 1; memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { if(gg[i] || vis[i]) continue; res++; queue<int> q; q.push(i); while(!q.empty()) { cnt = q.front(); q.pop(); if(gg[cnt] || vis[cnt]) continue; vis[cnt] = 1; int u = head[cnt]; for(int j = u; j != -1; j = edge[j].next) { q.push(edge[j].to); } } } } int main() { int a, b; memset(head, -1, sizeof(head)); memset(gg, 0, sizeof(gg)); scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) { scanf("%d %d", &a, &b); addedge(a, b); addedge(b, a); } res = 0, bfs(1); printf("%d\n",res); flag = false; scanf("%d", &k); while(k--) { memset(vis, 0, sizeof(vis)); scanf("%d", &v); res = 0; bfs(v); printf("%d\n",res); } return 0; }