题解 P1197 【[JSOI2008]星球大战】
主要思路：逆向思维
看到题目，第一个感觉，，，
连通块？？？
我刚学过的搜索呢？？？深搜广搜都可以啊QwQ！
但很多人都被困在了这个攻占星球（也就是去点）上。
如果再仔细看下题目，发现可以离线做这道题。
那么方法来了：
我们是不是可以把所有的边存下来，把被攻占的星球的顺序存下来，先把所有两端都没有被攻占的边加上，先求一遍连通块个数。然后反向的加点加边，边加边边求连通块个数，把答案反向存下来，然后正向输出。
这题结束了（伪）。于是代码如下：
代码1（20分）：
代码解释在最后的代码中
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 400400
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
int ans[mn], n, m, k;
struct edge{
int v,nxt/*,w*/;
} e[mn<<1];
int h[mn],p;
inline void add(int a,int b/*,int c*/){
p++;
e[p].nxt=h[a];
h[a]=p;
e[p].v=b;
//e[p].w=c;
}
int usd[mn];
pair<int, int> ee[mn];
bool not_alive[mn], vis[mn], not_in[mn];
void dfs(int x){
if(vis[x] && !not_alive[x])
return;
vis[x] = true;
rep(i,x){
if(!vis[e[i].v] && !not_alive[e[i].v])
dfs(e[i].v);
}
}
int main(){
n = read();
m = read();
go(i,1,m,1){
ee[i].first = read();
ee[i].second = read();
}
k = read();
memset(not_alive, false, sizeof(not_alive));
fo(i,k,1,1){
usd[i] = read();
not_alive[usd[i]] = true;
}
//cout << "
";
go(i, 1, m, 1){
if (!not_alive[ee[i].first] && !not_alive[ee[i].second]){
add(ee[i].first, ee[i].second);
add(ee[i].second, ee[i].first);
//cout << "111111111111111" << "
";
//cout << ee[i].first << " " << ee[i].second << "
";
}else{
not_in[i] = true;
}
}
int _ans = 0;
memset(vis, false, sizeof(vis));
_ans = 0;
go(i,0,n-1,1){
if(!vis[i] && !not_alive[i]){
dfs(i);
_ans++;
}
}
ans[k + 1] = _ans;
go(i,1,k,1){
not_alive[usd[i]] = false;
go(i,1,m,1){
if(not_in[i]){
if(!not_alive[ee[i].first] && !not_alive[ee[i].second]){
add(ee[i].first, ee[i].second);
add(ee[i].second, ee[i].first);
//cout << i << "
";
}
}
}
memset(vis, false, sizeof(vis));
_ans = 0;
go(i,0,n-1,1){
if(!vis[i] && !not_alive[i]){
dfs(i);
_ans++;
//cout << i << " ";
}
}
ans[k - i + 1] = _ans;
//cout << "
";
}
/*
memset(vis, false, sizeof(vis));
_ans = 0;
go(i,0,n-1,1){
if(!vis[i] && !not_alive[i]){
dfs(i);
_ans++;
}
}
cout << "
" << _ans;
*/
//cout << "
";
go(i,1,k+1,1){
cout << ans[i] << "
";
}
return 0;
}
20分？？？发生了什么？？？
TLE怎么办？？还有个RE QAQ
等等，RE是怎么回事？
是不是栈空间用的太多了？？dfs会占用一些栈空间。
这时我们会想到：并查集
如果把dfs找连通块改用并查集找连通块，会省下一些栈空间和一些添边的时间
于是，我们有了：
代码2（30分）
代码解释在最后的代码中
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 400400
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
int n, m, k, usd[mn], ans[mn];
pair<int, int> ee[mn];
bool not_alive[mn];
struct edge{
int v,nxt/*,w*/;
} e[mn<<1];
int h[mn],p;
inline void add(int a,int b/*,int c*/){
p++;
e[p].nxt=h[a];
h[a]=p;
e[p].v=b;
//e[p].w=c;
}
int father[mn];
inline int findx(int x){
return father[x] == x ? x : father[x] = findx(father[x]);
}
inline void mergex(int x,int y){
int xx = findx(x);
int yy = findx(y);
if (xx == yy)
return;
srand((unsigned)time(NULL));
if(rand()%2){
father[xx] = yy;
}else{
father[yy] = xx;
}
}
int main(){
n = read();
go(i,1,n,1){
father[i] = i;
}
m = read();
go(i,1,m,1){
ee[i].first = read();
ee[i].second = read();
add(ee[i].first, ee[i].second);
add(ee[i].second, ee[i].first);
}
k = read();
memset(not_alive, false, sizeof(not_alive));
fo(i,k,1,1){
usd[i] = read();
not_alive[usd[i]] = true;
}
int tot = n - k;
go(i,1,m,1){
if(!not_alive[ee[i].first] && !not_alive[ee[i].second]
&& findx(ee[i].first) != findx(ee[i].second)){
tot--;
mergex(ee[i].first, ee[i].second);
}
}
ans[k + 1] = tot;
go(i,1,k,1){
tot++;
not_alive[usd[i]] = false;
go(i,1,m,1){
if(!not_alive[ee[i].first] && !not_alive[ee[i].second]
&& findx(ee[i].first) != findx(ee[i].second)){
tot--;
mergex(ee[i].first, ee[i].second);
}
}
ans[k - i + 1] = tot;
}
go(i,1,k+1,1){
cout << ans[i] << "
";
}
return 0;
}
很好，RE没有了，TLE没有解决。
我们简单的分析一下可以发现，代码的复杂度是O(k*(n+m))的，，，WA！好大
我们分析一下我们哪个地方费的时间多。
对，在添点与找连通块数量上。如何优化这个地方？
我们可以发现，如果一个图n个点没有边，会有几个连通块？？
是不是有n个？
如果我们在其中两个点中加一条边的话，是不是连通块数量为n-1个？
那么我每当一条边加进去时，多了一个点加入一个连通块，那么总的连通块数就会-1？
这样的话，我们就可以先算出加点之前的连通块数，然后每加一个点，先把连通块数+1，然后看这个点是否可以连入其他连通块中（注：这里只需要把与这个点连接的边枚举出来就可以了），如果可以，连通块数-1，在每次操作后倒序记录连通块数，最后正序输出就好啦！
于是，我们有了——
代码3（再不AC这个题解就完了）：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 400400
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
int n, m, k, usd[mn], ans[mn];
pair<int, int> ee[mn];
bool not_alive[mn];
struct edge{
int v,nxt/*,w*/;
} e[mn<<1];
int h[mn],p;
inline void add(int a,int b/*,int c*/){
p++;
e[p].nxt=h[a];
h[a]=p;
e[p].v=b;
//e[p].w=c;
}
//链式前向星存图
int father[mn];
inline int findx(int x){
return father[x] == x ? x : father[x] = findx(father[x]);
}
inline void mergex(int x,int y){
int xx = findx(x);
int yy = findx(y);
if (xx == yy)
return;
srand((unsigned)time(NULL));//随机合并防止毒瘤出题人故意卡深度（自己都不知道会怎么并）
if(rand()%2){
father[xx] = yy;
}else{
father[yy] = xx;
}
}
//并查集
int main(){
n = read();
go(i,1,n,1){
father[i] = i;
}
m = read();
go(i,1,m,1){
ee[i].first = read();//离线判断用
ee[i].second = read();
add(ee[i].first, ee[i].second);//存图
add(ee[i].second, ee[i].first);
}
k = read();
memset(not_alive, false, sizeof(not_alive));//玄学初始化
fo(i,k,1,1){
usd[i] = read();//倒序记录被炸的顺序
not_alive[usd[i]] = true;//记录哪个点 最后被炸掉了
}
int tot = n - k;//重点！这里记录目前剩的点数
go(i,1,m,1){//然后先把存活的点之间的边连上，放到一个集合里，总的连通块数-1
if(!not_alive[ee[i].first] && !not_alive[ee[i].second]
&& findx(ee[i].first) != findx(ee[i].second)){
tot--;
mergex(ee[i].first, ee[i].second);
}
}
ans[k + 1] = tot;
go(i,1,k,1){
tot++;
not_alive[usd[i]] = false;
for (int j = h[usd[i]]; j; j = e[j].nxt){//枚举与这个点连接的点，看会合并几次，合并几次就会减少几个连通块
if(!not_alive[e[j].v] && findx(e[j].v) != findx(usd[i])){
tot--;
mergex(e[j].v, usd[i]);
}
}
ans[k - i + 1] = tot;//倒序存储
}
go(i,1,k+1,1){//正序输出
cout << ans[i] << "
";
}
return 0;
}