题解
抽象化
抽象成点和边,对于抹除一个点,判断整个图是否联通
等价于建立一个点(被抹除点的前一个点),判断这个点与周围点相连后,累积合并次数是否等于点数减一
code
#define ll long long
#include<bits/stdc++.h>
using namespace std;
ll fa[200005];
ll finds(ll now){return (fa[now]=(now==fa[now])?now:finds(fa[now]));}
ll ans[200005]={0};
ll open[200005]={0},bing=0,shut[200005]={0};
vector<ll> G[200005];
inline void read(ll &x) {
x = 0;
ll flag = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')flag = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
x *= flag;
}
inline void write(ll x)
{
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
int main()
{
ll n,m;
read(n);read(m);
for(ll i=1;i<=n;i++)fa[i]=i;
for(ll i=1;i<=m;i++)
{
ll x,y;
read(x);read(y);
G[x].push_back(y);
G[y].push_back(x);
}
for(ll i=1;i<=n;i++) read(shut[i]);
for(ll i=n;i>=1;i--)
{
ll x=shut[i];
open[x]=1;
for(auto to:G[x]) if(open[to]&&finds(to)!=x&&(++bing)) fa[finds(to)]=x;
ans[i]=(bing==n-i?1:0);
}
for(ll i=1;i<=n;i++) puts((ans[i]==1)?"YES":"NO");
return 0;
}
标签:P6121,Farm,ll,fa,Closing,now,open,finds,200005
From: https://www.cnblogs.com/pure4knowledge/p/18060898