思路

题目要求询问有多少个连通块，不难想到使用并查集。但是并查集我们只会添加边，并不会删除边，这咋整？

注意到删除边的逆操作就是添加边（废话），可以倒着进行每一个查询，删除边的操作就变为了添加边。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{int x,y;}e[N];
int fa[N],siz[N];
int ans[N];
int find(int x)
{
	if(fa[x]==x)return x;
	int fax=find(fa[x]);
	siz[x]=siz[fax];
	fa[x]=fax;
	return fax;
}
signed main()
{
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)scanf("%lld%lld",&e[i].x,&e[i].y);
	for(int i=1;i<=n;i++)siz[i]=1,fa[i]=i;
	for(int i=m;i>=1;i--)
	{
		int tx=find(e[i].x),ty=find(e[i].y);
		if(tx!=ty)
		{
			ans[i]=ans[i+1]+siz[tx]*siz[ty];
			siz[ty]+=siz[tx];
			fa[tx]=ty;
		}
		else ans[i]=ans[i+1];
	}
	for(int i=1;i<=m;i++)printf("%lld\n",n*(n-1)/2-ans[i+1]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define int long long
int fa[N], siz[N], x[N], y[N], ans[N];
int findfa(int x){return (fa[x] == x) ? x : fa[x] = findfa(fa[x]);}
void merge(int x, int y)
{
	int xfa = findfa(x), yfa = findfa(y);
	fa[xfa] = yfa;
	siz[yfa] += siz[xfa];
}
signed main()
{
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
	for (int i = 1; i <= m; i++) cin >> x[i] >> y[i];
	int cnt = 0.5 * (double)n * (double)(n - 1);
	for (int i = m; i >= 1; i--)
	{
		ans[i] = cnt;
		int xfa = findfa(x[i]), yfa = findfa(y[i]);
		if (xfa != yfa) cnt -= siz[xfa] * siz[yfa], merge(xfa, yfa);
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
struct node{int x,y;}e[N];
int fa[N],siz[N],res[N];
int findfa(int x){return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);}
signed main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>e[i].x>>e[i].y;
	int ans=n*(n-1)/2;
	for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
	for(int i=m;i>=1;i--)
	{
		res[i]=ans;
		int tx=findfa(e[i].x),ty=findfa(e[i].y);
		if(tx!=ty)
		{
			ans-=siz[tx]*siz[ty];
			fa[tx]=ty,siz[ty]+=siz[tx];
		}
	}
	for(int i=1;i<=m;i++)cout<<res[i]<<'\n';
	return 0;
}