卷王 @ 2023-01-21 10:50:54
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000007;
struct node
{
int nxt, to, from;
}e[maxn];
int n, m, k, x, y, tot, cnt = 0;
int h[maxn];
int a[maxn], f[maxn];
int ans[maxn];
bool vis[maxn];
inline int find(int x)
{
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
inline void add(int u, int v)
{
e[++cnt].from = u;
e[cnt].nxt = h[u];
e[cnt].to = v;
h[u] = cnt;
}
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; i++)
f[i] = i;
for(int i = 1; i <= m; i++)
{
x = read(), y = read();
add(x, y); add(y, x);
}
k = read();
for(int i = 1; i <= k; i++)
{
a[i] = read();
vis[a[i]] = 1;
}
tot = n - k;
for(int i = 1; i <= m * 2; i++)
{
int u = e[i].from, v = e[i].to;
if(vis[u] == 0 && vis[v] == 0 && f[find(u)] != f[find(v)])
{
tot--;
f[find(u)] = f[find(v)];
}
}
ans[k + 1] = tot;
for(int i = k; i >= 1; i--)
{
int u = a[i]; vis[u] = 0;
tot++;
for(int j = h[u]; j; j = e[j].nxt)
{
int v = e[i].to;
if(vis[v] == 0 && f[find(u)] != f[find(v)])
{
tot--;
f[find(u)] = f[find(v)];
}
}
ans[i] = tot;
}
for(int i = 1; i <= k + 1; i++)
printf("%d\n", ans[i]);
return 0;
}
by Algae_qwq @ 2023-01-21 11:20:07
头像好评
by Loser_Syx @ 2023-01-21 11:46:59
我记得lz之前的头像是kkk的
by W2011cx @ 2023-01-21 11:52:22
我甚至以为这是兔队的帖子
by Fragile_like_bomb @ 2023-01-21 12:05:39
mpft