bzoj1015 [JSOI2008]星球大战starwar 并查集

题目描述

---

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

输入输出格式

---

输入格式：

---

输入文件第一行包含两个整数，N (1 <= N <= 2M) 和M (1 <= M <= 200,000)，分别表示星球的数目和以太隧道的数目。星球用0~N-1的整数编号。 接下来的M行，每行包括两个整数X, Y，其中（0<=X<>Y

输出格式：

---

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

说明

---

[JSOI2008]

Analysis

---

显然并查集，离线做要倒着来 这里最大的n和最大的m实际上是相等的，这就比较坑了MLE要注意的

Code

---

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> #define debug puts("-----") #define rep(i, st, ed) for (int i = st; i <= ed; i += 1) #define drp(i, st, ed) for (int i = st; i >= ed; i -= 1) #define fill(x, t) memset(x, t, sizeof(x)) #define min(x, y) x<y?x:y #define max(x, y) x>y?x:y #define PI (acos(-1.0)) #define EPS (1e-8) #define INF (1<<30) #define ll long long #define db double #define ld long double #define pb push_back #define N 400011 #define E N #define MOD 100000007 #define L 255 using namespace std; struct edge{int x, y, next;}e[E]; int fa[N], ls[N], v[N]; bool bct[N]; inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v; } inline int addEdge(int &cnt, const int &x, const int &y){ e[++ cnt] = (edge){x, y, ls[x]}; ls[x] = cnt; return 0; } inline int getFather(const int &now){ return now == fa[now]? now: fa[now] = getFather(fa[now]); } inline int merge(const int &x, const int &y){ int fx = getFather(x), fy = getFather(y); if (fx ^ fy){ fa[fx] = fy; return 1; } return 0; } inline int init(const int &n){ rep(i, 1, n){ fa[i] = i; } } inline int stcs(const int &n){ int cnt = 0; rep(i, 1, n){ if (fa[i] == i && !bct[i]){ cnt += 1; } } return cnt; } int main(void){ int n = read(), m = read(); int edgeCnt = 0; init(n); rep(i, 1, m){ int x = read() + 1, y = read() + 1; addEdge(edgeCnt, x, y); addEdge(edgeCnt, y, x); merge(x, y); } printf("%d\n", stcs(n)); int k = read(); rep(i, 1, k){ int opt = read() + 1; bct[opt] = 1; v[++ v[0]] = opt; } init(n); rep(i, 1, edgeCnt){ if (!bct[e[i].x] && !bct[e[i].y]){ merge(e[i].x, e[i].y); } } int tot = stcs(n); drp(index, v[0], 1){ int now = v[index]; bct[now] = 0; v[index] = tot; for (int i = ls[now]; i; i = e[i].next){ if (!bct[e[i].y]){ tot -= merge(e[i].x, e[i].y); } } tot += 1; } rep(index, 1, v[0]){ printf("%d\n", v[index]); } // printf("size = %d\n", int(ans.size())); return 0; }