BZOJ1015: [JSOI2008]星球大战starwar【并查集】【傻逼题】

Description

　　很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

Input

　　输入文件第一行包含两个整数，N (1 < = N < = 2M) 和M (1 < = M < = 200,000)，分别表示星球的数目和以太隧道的数目。星球用 0 ~ N-1的整数编号。接下来的M行，每行包括两个整数X, Y，其中（0 < = X <> Y 表示星球x和星球y之间有“以太”隧道，可以直接通讯。接下来的一行为一个整数k，表示将遭受攻击的星球的数目。接下来的k行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这k个数互不相同，且都在0到n-1的范围内。

Output

第一行是开始时星球的连通块个数。接下来的K行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

Sample Input

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

Sample Output

1

1

1

2

3

3

就是删点，倒着来加入每个点

顺便维护一下并查集和联通块个数就可以了

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

typedef pair<int, int> pi;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 4e5 + 10;

int U[N], V[N], vis[N];

int fa[N], n, m, k, siz;

int a[N], ans[N];

vector<int> edge[N];

int Find(int x) {

  return x == fa[x] ? x : fa[x] = Find(fa[x]);

}

void merge(int x, int y) {

  int fax = Find(x), fay = Find(y);

  if (fax == fay) return;

  --siz;

  fa[fax] = fay;

}

int main() {

  Read(n), Read(m);

  fu(i, 1, n) fa[i] = i, vis[i] = 1;

  fu(i, 1, m) {

    int u, v;

    Read(u), Read(v);

    ++u, ++v;

    edge[u].push_back(v);

    edge[v].push_back(u);

  }

  Read(k);

  fu(i, 1, k) {

    Read(a[i]); ++a[i];

    vis[a[i]] = 0;

  }

  siz = n - k;

  fu(i, 1, n) if (vis[i])

    fv(j, edge[i]) if (vis[edge[i][j]])

      merge(i, edge[i][j]);

  fd(i, k, 1) {

    ans[i] = siz;

    ++siz, vis[a[i]] = 1;

    fv(j, edge[a[i]]) if (vis[edge[a[i]][j]])

      merge(a[i], edge[a[i]][j]);

  }

  ans[0] = siz;

  fu(i, 0, k) Write(ans[i]), putchar('\n');

  return 0;

}

巴特西