题解 – P1197 [JSOI2008] 星球大战

[题目链接] – [JSOI2008] 星球大战

[JSOI2008] 星球大战

题目描述

给定一张无向图G=(n,m)，共有n个点和m条边，没有边权。在k的时间范围之内，会依次删除一些点。求出t=0 \sim k时的连通块个数。

样例 #1

样例输入 #1

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

样例输出 #1

1
1
1
2
3
3

提示

【数据范围】
对于 100\% 的数据，1\le m \le 2\times 10^5，1\le n \le 2m，x \neq y。

分析

连通块的个数可以用并查集确定，但是并查集如何删除连接？这是一个问题。
于是我们将时间倒过来，先将所有该拆的点都拆掉，慢慢加回来，此时我们只需要看依次加回来的点是否跟剩下的图连通。
注意删除一个点之后，在未被删除中的点中判断连通块。

做法

1.初始化原图，使用链式前向星建图。
2.读入删除顺序，建立一个vis数组，将删除的点全部标记为1。
3.初始化一个tot变量，这是此时的连通块数量，值为n-k。
4.跑一遍所有的边，如果该边两头的点vis=0，连接并tot–。
5.倒序加点，初始化tot++，查看这个点的所有边，如果可以连通，连接并tot–。

Code

#include
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int M = 2e5 + 10;
const int N = 4e5 + 10;
int n, m, k;
int x, y, z[M];
int vis[N];
struct edge{int from, to, nxt;}G[M << 1]; // 链式前向星
int cnt = 1, head[N];
inline void add_edge(int u, int v) {G[cnt] = (edge){u, v, head[u]}; head[u] = cnt++;}
int fa[N]; //并查集
inline void init() {for(int i = 1; i <= n; i++) {fa[i] = i;} memset(head, -1, sizeof(head));}
int find(int pos) {if(fa[pos] != pos) {fa[pos] = find(fa[pos]);} return fa[pos];}
inline void merge(int posx, int posy) {if(find(posx) != find(posy)) fa[find(posx)] = find(posy);}
inline int check(int posx, int posy) {return find(posx) == find(posy);}
int main()
{
  scanf("%d%d", &n, &m);
  init();
  for(int i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    add_edge(x, y);
    add_edge(y, x);
  }
  scanf("%d", &k);
  for(int i = 1; i <= k; i++) {
    scanf("%d", &z[i]);
    vis[z[i]] = 1;
  }
  stack ans;
  int tot = n - k;
  for(int i = 1; i <= m << 1; i++) {
    if(!vis[G[i].from] && !vis[G[i].to] && !check(G[i].from, G[i].to)) {tot--; merge(G[i].from, G[i].to);}
  }
  ans.emplace(tot);
  for(int i = k; i >= 1; i--) {
    vis[z[i]] = 0;
    tot++;
    for(int j = head[z[i]]; j != -1; j = G[j].nxt) {
      if(!vis[G[j].to] && !check(G[j].from, G[j].to)) {tot--; merge(G[j].from, G[j].to);}
    }
    ans.emplace(tot);
  }
  while(!ans.empty()) {printf("%d\n", ans.top()); ans.pop();}
  return 0;
}