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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 400005;
int n, m, num, h[N], k, p[N], ans[N], fa[N];
int head[N], tmp;
struct node {
int to = -1, next = -1;
} e[N << 2];
struct edge {
int to, next;
} q[N];
void add(int x, int y) {
e[++tmp].to = y;
e[tmp].next = head[x];
head[x] = tmp;
}
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
x = find(x);
y = find(y);
fa[y] = x;
}
int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = (s << 1) + (s << 3) + ch - '0';
ch = getchar();
}
return s * w;
}
bool book[N];
signed main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) fa[i] = i, head[i] = -1;
for (int i = 1; i <= m; i++) {
int x = read(), y = read();
add(x, y);
add(y, x);
q[i * 2 - 1] = {x, y};
q[i * 2] = {y, x};
}
k = read();
for (int i = 1; i <= k; i++) {
p[i] = read();
book[p[i]] = true;
}
num = n - k;
for (int i = 1; i <= 2 * m; i++) {
if (!book[q[i].to] && !book[q[i].next] && find(q[i].to) != find(q[i].next)) {
num--;
merge(q[i].to, q[i].next);
}
}
ans[k + 1] = num;
for (int i = k; i >= 1; i--) {
book[p[i]] = false;
num++;
for (int j = head[p[i]]; j != -1; j = e[j].next) {
if (!book[e[j].to] && find(p[i]) != find(e[j].to)) {
num--;
merge(p[i], e[j].to);
}
}
ans[i] = num;
}
for (int i = 1; i <= k + 1; i++) cout << ans[i] << endl;
return 0;
}
|