[USACO16OPEN]Closing the Farm 题解

本文主要是介绍[USACO16OPEN]Closing the Farm 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题有两道一模一样的题目，改个数据范围即可 AC。

题目1 | 题目2

题意简述

给定一张无向图，每次删去一个点，问每次操作后图是否联通。

分析

判断图是否联通可以想到使用并查集来维护。但是并查集很难实现删除操作，那如何处理呢？

并查集的核心是“并”和“查”，既然题目要求每次删去一个点，那不如反过来想，倒序处理，把删点变成加点，这样处理起来就非常方便快捷了。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,m;struct edge
{int to,nxt;
}e[3005<<1];
int head[3005];
int idx;
void link(int x,int y){e[++idx].to=y;e[idx].nxt=head[x];head[x]=idx;
}
//建图
int fa[3005];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
//并查集
int del[3005];//每次删去的点
int f[3005];//f[i]表示第i次操作图是否联通int main(){cin>>n>>m;for(int i=1,x,y;i<=m;i++){cin>>x>>y;link(x,y);link(y,x);}for(int i=1;i<=n;i++)cin>>del[i];int cnt=0;for(int i=n;i>=1;i--){int cur=del[i];fa[cur]=cur;cnt++;//加入新点，没有任何联系，自成一块for(int j=head[cur];j;j=e[j].nxt){int v=e[j].to;if(fa[v]){//若已加入图中，方可合并int x=find(v),y=find(cur);if(x!=y){fa[x]=y;cnt--;//合并，连通分量数量减少}}}if(cnt==1)f[i]=true;//联通}for(int i=1;i<=n;i++)puts(f[i]?"YES":"NO");return 0;
}