并查集+逆序
首先读入相连的点，但这里不能直接合并建立并查集，因为并查集没有Ctrl+Z操作(就是无法分离两个已经合并的集合)，所以我们要先存起来，等所有的询问都读入之后，倒着进行操作。
我们考虑怎样倒着操作：
首先，读入数据，把所有的数据都存起来，其中x[i],y[i]表示第i次读入的关系，order[i]表示第i次读入的数是多少，ss[i]表示i是否在并查集里面，如果存在，则为0，不存在则为1。
接着，倒着处理读入的询问。从第i=n次开始，把与点order[i]有关的边读入，合并并查集，之后在把和该点有关的所有的可加入的边都加入并查集以后，判断并查集中集合的个数，并记录在ans[i]中，然后i--，重复以上步骤。
最后，从1开始到n-1，判断ans是否为1，如果为1，说明所有的点都是联通的（只有一个并查集），输出YES，否则输出NO，第n次询问的时候，所有的点都已经从并查集删除，因此一定是联通的，输出YES。
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,g[3001],x[3001],y[3001],order[3001],ss[3001],ans[3001],w;
//x[i],y[i]表示第i次读入的关系，order[i]表示第i次读入的数是多少，ss[i]表示i是否在并查集里面，如果存在，则为0，不存在则为1
//g[i]存储并查集，ans[i]存储第i次询问时并查集中有多少个集合。
int find(int u)
{
if(g[u]!=u)g[u]=find(g[u]);
return g[u];
}
void merg(int u,int v)
{
u=find(u);
v=find(v);
if(u==v)return;
g[u]=v;
}
int main()
{
memset(ss,0,sizeof(ss));
scanf("%d%d",&n,&m);
for(int j=1;j<=n;j++)g[j]=j;
for(int i=1;i<=m;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
{
scanf("%d",&w);
order[i]=w;
ss[w]=1;//不在并查集内
}
for(int i=n;i>0;i--)
{
ss[order[i]]=0;//由于倒序，此时它被建造
for(int j=1;j<=m;j++)
if(ss[x[j]]==0&&ss[y[j]]==0)//建造后可以合并
merg(x[j],y[j]);
ans[n]=0;
for(int j=1;j<=n;j++)
if(find(j)==j&&ss[j]==0)//为并查集的根（在并查集内且为自己祖先）
ans[i]++;
}
for(int i=1;i<=n-1;i++)
if(ans[i]==1)printf("YES\n");//只有一个并查集
else printf("NO\n");//多个并查集不连通
printf("YES");
return 0;
}
P3144 [USACO16OPEN]Closing the Farm S
原文：https://www.cnblogs.com/ruanmowen/p/12731043.html