星球大戰(zhàn) JSOI2008 并查集

2019-11-11 06:37:23

字體：大中小

來源：轉載

供稿：網友

題目描述

很久以前，在一個遙遠的星系，一個黑暗的帝國靠著它的超級武器統(tǒng)治者整個星系。某一天，憑著一個偶然的機遇，一支反抗軍摧毀了帝國的超級武器，并攻下了星系中幾乎所有的星球。這些星球通過特殊的以太隧道互相直接或間接地連接。但好景不長，很快帝國又重新造出了他的超級武器。憑借這超級武器的力量，帝國開始有計劃地摧毀反抗軍占領的星球。由于星球的不斷被摧毀，兩個星球之間的通訊通道也開始不可靠起來。現(xiàn)在，反抗軍首領交給你一個任務：給出原來兩個星球之間的以太隧道連通情況以及帝國打擊的星球順序，以盡量快的速度求出每一次打擊之后反抗軍占據(jù)的星球的連通快的個數(shù)。（如果兩個星球可以通過現(xiàn)存的以太通道直接或間接地連通，則這兩個星球在同一個連通塊中）。

輸入輸出格式

輸入格式：

輸入文件第一行包含兩個整數(shù)，N (1 <= N <= 2M) 和M (1 <= M <= 200,000)，分別表示星球的數(shù)目和以太隧道的數(shù)目。星球用0~N-1的整數(shù)編號。接下來的M行，每行包括兩個整數(shù)X, Y，其中（0<=X<>Y

輸出格式：

輸出文件的第一行是開始時星球的連通塊個數(shù)。接下來的K行，每行一個整數(shù)，表示經過該次打擊后現(xiàn)存星球的連通塊個數(shù)。

說明

[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 255using 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); }