当前位置: 代码迷 >> 综合 >> bzoj4579[Usaco2016 Open]Closing the Farm--by lethalboy
  详细解决方案

bzoj4579[Usaco2016 Open]Closing the Farm--by lethalboy

热度:132   发布时间:2023-09-30 17:45:58.0

如果按照正常的思维方式从前向后依次操作下去,会发现这是一个无向图上逐渐消去点找强连通分量数的过程,那么就想到用并查集了,而并查集作用在于合并而非分离,故倒着做来达到合并强连通分量的过程。这样就简单了。

今天开始做rsk大神的题表

%%%BraketBN%%%

(膜大神,RP++)

附代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#define N 200020
#include<vector>
using namespace std;
int read()
{int x=0,f=1;char ch;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m;
bool vis[N],ok[N];
vector<int>G[N];
int a[N],f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main()
{n=read(),m=read();for(int i=1,a,b;i<=m;i++){scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a);}for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=i;int cnt=0;for(int i=n;i;i--){int u=a[i];cnt++;vis[u]=1;for(int j=0;j<G[u].size();j++){int v=G[u][j];if(!vis[v])continue;int fa=find(u),fb=find(v);if(fa!=fb){if(fa>fb)swap(fa,fb);f[fb]=fa;cnt--;}}if(cnt==1)ok[i]=1;}for(int i=1;i<=n;i++)if(ok[i])printf("YES\n");else printf("NO\n");
}</span><span style="font-size: 24px;">
</span>


  相关解决方案