Problem Statement
很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。
某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。
现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。
输入文件第一行包含两个整数，$n,m$，分别表示星球的数目和以太隧道的数目。星球用 $0 \sim n-1$ 的整数编号。
接下来的 $m$ 行，每行包括两个整数 $x,y$，表示星球 $x$ 和星球 $y$ 之间有 “以太” 隧道，可以直接通讯。
接下来的一行为一个整数 $k$ ，表示将遭受攻击的星球的数目。
接下来的 $k$ 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 $k$ 个数互不相同，且都在 $0$ 到 $n-1$ 的范围内。
Output
第一行是开始时星球的连通块个数。接下来的 $k$ 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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
Constraints
对于 $100%$ 的数据，$1\le m \le 2\times 10^5$，$1\le n \le 2m$，$x \neq y$。
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
const int N = 4e5+10;
const int M = 2e5+10;
int cnt = 0;
int head[N],broky[N],ans[N];
bool smashed[N];//表示此时第i个星球是否被摧毁
struct Edge
{
int from,to,next;//链式前向星存图
}edge[N];//双向建边，边数要开到2*M也就是N
void add(int u,int v)
{
cnt++;
edge[cnt].from = u;
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
struct DSU
{
vector<int> fa,Size;
DSU(int n) : fa(n+1),Size(n+1,1)
{
iota(fa.begin(),fa.end(),0);
}
int find(int x)
{
//注意此时路径压缩是在find()函数里进行的，所以比对是否为同一集合应该用same()函数或者find()函数比对
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
bool same(int x, int y)
{
return find(x) == find(y);
}
bool merge(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return false;
if(x > y) swap(x, y);
Size[x] += Size[y];//按秩 小 + 大
fa[y] = x;//大序号的父亲->小序号
return true;
}
int size(int x)
{
return Size[find(x)];
}
};
void solve()
{
int n,m;
cin >> n >> m;
DSU dsu(n-1);
for(int i=1;i<=m;i++)
{
int x,y;
cin >> x >> y;
add(x,y);//双向通信，双向建边
add(y,x);
}
int k;
cin >> k;
int total = n - k;//初始化所有的被摧毁后的星球此时都是单独的连通块，所以此时连通块数量为n-k
for(int i=1;i<=k;i++)
{
cin >> broky[i];//表示第i个被摧毁的星球
smashed[broky[i]] = true;//表示第i个星球是否被摧毁
}
for(int i=1;i<=2*m;i++)//要遍历到2m，因为是双向图，要两边都判断
{
if(!smashed[edge[i].from]&&!smashed[edge[i].to])//如果u和v都不是被摧毁的
{
if(!dsu.same(edge[i].from,edge[i].to))//则建立连接
{
total--;//连通块个数-1
dsu.merge(edge[i].from,edge[i].to);
}
}
}
ans[k+1] = total;//所有星球都摧毁后剩下的连通块个数
for(int i=k;i>=1;i--)
{
int temp = broky[i];//表示当前被重建的星球是temp
total++;//重建后连通块+1
smashed[temp] = false;
for(int j=head[temp];j;j=edge[j].next)//链式前向星遍历这个星球连接的每一条边
{
if(!smashed[edge[j].to]&&!dsu.same(edge[j].from,edge[j].to))//如果这个边连接的星球此时没有被摧毁，而且也不是与temp联通的
{
total--;//连通块-1
dsu.merge(edge[j].to,edge[j].from);//联通这两个星球
}
}
ans[i] = total;//更新此时的连通块数量
}
for(int i=1;i<=k+1;i++)
{
cout << ans[i] << endl;
}
}
|