https://www.luogu.org/problem/P1197
This question is an enhanced version of closing the farm. The data is a bit large, and the matrix cannot be saved;
It is also a record deletion operation, adding edges from back to front;< /p>
first count each point as a connected block, and then reduce the number of connected blocks for each connected edge by one;
When adding a point, don’t forget the number of connected blocks +1, then merge;
There are still arrays to be enlarged;
#include
#include
#include
using namespace std;
const int maxn=400010;
int pre[maxn*2],last[ maxn],other[maxn*2],from[maxn*2],l;
int n,m,k;
int out_block[maxn*2],delete_order[ maxn*2];
int num_block[maxn*2],tot_block;
int father[maxn*2];
void add(int x,int y)
{
l++;
from[l]=x;
pre[l]=last[x];
last[x]=l;
other[l]=y;
}
int getfather(int x)
{
if(father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
}
void merge(int x,int y)
{
int fx=getfather(x);
int fy=getfather(y);
father[fx]=fy;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&delete_order[i]);
out_block[delete_order[i]]=1;
}
tot_block=n-k;
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m*2;i++)
{
if(!out_block[from[i]] &&!out_block[other[i]]&&getfather(from[i])!=getfather(other[ i]))
{
merge(from[i],other[i]);
tot_block--;
}
}
num_block[k+1]=tot_block;
for(int i=k;i>= 1;i--)
{
out_block[delete_order[i]]=0;
tot_block++;
for(int p=last[delete_order[i ]];p;p=pre[p])
{
int v=other[p];
if(!out_block[v]&&getfather(delete_order[i])!=getfather(v))
{
tot_block--;
merge(delete_order[i],v);
}
}
num_block[i]=tot_block;
}
for(int i=1;i<=k+1;i++)
{
printf("%d ",num_block[i]);
}
return 0;
}
#include
#include
#include
using namespace std;
const int maxn=400010;
int pre[maxn*2],last[ maxn],other[maxn*2],from[maxn*2],l;
int n,m,k;
int out_block[maxn*2],delete_order[ maxn*2];
int num_block[maxn*2],tot_block;
int father[maxn*2];
void add(int x,int y)
{
l++;
from[l]=x;
pre[l]=last[x];
last[x]=l;
other[l]=y;
}
int getfather(int x)
{
if(father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
}
void merge(int x,int y)
{
int fx=getfather(x);
int fy=getfather(y);
father[fx]=fy;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&delete_order[i]);
out_block[delete_order[i]]=1;
}
tot_block=n-k;
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m*2;i++)
{
if(!out_block[from[i]] &&!out_block[other[i]]&&getfather(from[i])!=getfather(other[ i]))
{
merge(from[i],other[i]);
tot_block--;
}
}
num_block[k+1]=tot_block;
for(int i=k;i>= 1;i--)
{
out_block[delete_order[i]]=0;
tot_block++;
for(int p=last[delete_order[i ]];p;p=pre[p])
{
int v=other[p];
if(!out_block[v]&&getfather(delete_order[i])!=getfather(v))
{
tot_block--;
merge(delete_order[i],v);
}
}
num_block[i]=tot_block;
}
for(int i=1;i<=k+1;i++)
{
printf("%d ",num_block[i]);
}
return 0;
}