vector存图,样例没过
#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[400005];
int n, m;
int k;
int des[400005];
int cntlian;
int fa[400005];
int ans[400005];
bool broken[400005];
struct edge
{
int u, v;
}e[400005];
int cnt = 0;
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= m;i ++)
{
int u, v;
cin >> u >> v;
e[++ cnt] = edge{u, v};
e[++ cnt] = edge{v, u};
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> k;
cntlian = n - k;
for(int i = 1;i <= k;i ++)
{
cin >> des[i];
broken[des[i]] = true;
}
for(int i = 0;i < n;i ++) fa[i] = i;
for(int i = 1;i <= 2 * m;i ++)
{
if(!broken[e[i].u] && !broken[e[i].v])
{
int fu = find(e[i].u);
int fv = find(e[i].v);
if(fu != fv)
{
fa[fv] = fu;
cntlian --;
}
}
}
ans[k + 1] = cntlian;
for(int i = k;i >= 1;i --)//貌似这部分有问题
{
int u = des[i];
cntlian ++;
broken[u] = false;
for(int j = 0;j < adj[u].size();j ++)
{
int v = adj[u][i];
if(broken[v]) continue;
int fu = find(u);
int fv = find(v);
if(fu != fv)
{
fa[fv] = fu;
cntlian --;
}
}
ans[i] = cntlian;
}
for(int i = 1;i <= k + 1;i ++)
{
cout << ans[i] << endl;
}
return 0;
}