日月童羽 @ 2019-08-24 10:26:03
10分求助!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
int n, m, p, oo, ll[400005], tot, ans[400005], fa[400005];
bool bj[400005];
int a[400005], b[400005][3];
int find(int x)
{
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void lianjie(int from, int next)
{
b[oo][0] = from;
b[oo][2] = a[from];
b[oo][1] = next;
a[from] = oo;
oo++;
}
int main ()
{
// freopen("out","r",stdin);
cin >> n >> m;
for(int i = 0; i < n; i++)
{
fa[i] = i;
a[i] = -1;
}
for(int i = 0; i < m; i++)
{
int k, l;
// oo = i;
cin >> k >> l;
lianjie(k, l);
lianjie(l, k);
}
cin >> p;
tot = n - p;
for(int i = 1; i <= p; i++)
{
int pp;
cin >> pp;
bj[pp] = 1;
ll[i] = pp;
}
for(int i = 0; i < 2 * m; i++)
{
if(!bj[b[i][0]] && !bj[b[i][1]])
{
if(find(b[i][0]) != find(b[i][1]))
{
tot--;
fa[find(b[i][0])] = fa[find(b[i][1])];
}
}
}
ans[p + 1] = tot;
for(int i = p; i >= 1; i--)
{
bj[i] = 0;
int xx = ll[i];
tot++;
int yy = a[xx];
while(yy != -1)
{
// cout << "shdfkjhs" << " ";
if(find(b[yy][0]) != find(b[yy][1]) && !bj[b[yy][1]])
{
tot--;
fa[find(b[yy][1])] = fa[find(b[yy][0])];
}
yy = b[yy][2];
}
ans[i] = tot;
}
for(int i = 1; i <= p + 1; i++)
{
cout << ans[i] << endl;
}
}