bzoj 4579 [Usaco2016 Open]Closing the Farm
4579: [Usaco2016 Open]Closing the Farm
Time Limit: 10 Sec
Memory Limit: 128 MB
Submit: 132
Solved: 80
[Submit][Status][Discuss]
Description
Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporar
ily close down his farm to save money in the meantime.The farm consists of NN barns connected with M
M bidirectional paths between some pairs of barns (1≤N,M≤200,000). To shut the farm down, FJ plans
to close one barn at a time. When a barn closes, all paths adjacent to that barn also close, and ca
n no longer be used.FJ is interested in knowing at each point in time (initially, and after each clo
sing) whether his farm is "fully connected" -- meaning that it is possible to travel from any open b
arn to any other open barn along an appropriate series of paths. Since FJ's farm is initially in som
ewhat in a state of disrepair, it may not even start out fully connected.
Input
The first line of input contains N and M. The next M lines each describe a path in terms of the pair
of barns it connects (barns are conveniently numbered 1…N). The final N lines give a permutation o
f 1…N describing the order in which the barns will be closed.
Output
The output consists of N lines, each containing "YES" or "NO". The first line indicates whether the
initial farm is fully connected, and line i+1 indicates whether the farm is fully connected after th
e iith closing.
Sample Input
4 3
1 2
2 3
3 4
3
4
1
2
Sample Output
YES
NO
YES
YES
HINT
Source
Gold
【分析】
USACO签到题第二弹...
考虑反着加点,并查集维护当前连通块个数
【代码】
//bzoj 4579
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=200005;
int n,m,cnt,num;
bool vis[mxn];
int cut[mxn],father[mxn],head[mxn],ans[mxn];
struct edge {int next,to;} f[mxn<<1];
inline void add(int u,int v)
{
f[++cnt].to=v,f[cnt].next=head[u],head[u]=cnt;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
inline int find(int x)
{
if(x!=father[x]) father[x]=find(father[x]);
return father[x];
}
int main()
{
int i,j,u,v,t1,t2;
n=read(),m=read();
fo(i,1,n) father[i]=i;
fo(i,1,m)
{
u=read(),v=read();
add(u,v),add(v,u);
}
for(i=n;i>=1;i--) cut[i]=read();
fo(i,1,n)
{
u=cut[i],vis[u]=1,num++;
for(int j=head[u];j;j=f[j].next)
{
t1=find(u);
v=f[j].to;
if(!vis[v]) continue;
t2=find(v);
if(t1!=t2) father[t1]=t2,num--;
}
ans[i]=num;
}
for(i=n;i;i--)
if(ans[i]==1) printf("YES\n");
else printf("NO\n");
return 0;
}