前言

今天zty带来的是P6121 [USACO16OPEN] Closing the Farm G，大家给个赞呗， zty开学了，更新是会变少的，这个学期是zty的毕业学期了，过完这学期zty就毕业了

加个技术交流裙：953793685

先 赞 后 看 养 成 习 惯

先 赞 后 看 养 成 习 惯
演示用编译器及其标准
Dev C++ 6.7.5 Red panda C++14

正文

P6121 [USACO16OPEN] Closing the Farm G

题目背景

本题和 银组同名题目 在题意上一致，唯一的不同是数据范围。

题目描述

FJ 和他的奶牛们正在计划离开小镇做一次长的旅行，同时 FJ 想临时地关掉他的农场以节省一些金钱。

这个农场一共有被用 $M$ 条双向道路连接的 $N$ 个谷仓（$1\le N,M\le 2\times 10^5$）。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

FJ 现在正感兴趣于知道在每一个时间（这里的“时间”指在每一次关闭谷仓之前的时间）时他的农场是否是“全连通的”——也就是说从任意的一个开着的谷仓开始，能够到达另外的一个谷仓。注意自从某一个时间之后，可能整个农场都开始不会是“全连通的”。

输入格式

输入第一行两个整数 $N,M$。

接下来 $M$ 行，每行两个整数 $u,v$（$1\le u,v\le N$），描述一条连接 $u,v$ 两个农场的路。

最后 $N$ 行每行一个整数，表示第 $i$ 个被关闭的农场编号。

输出格式

输出 $N$ 行，每行包含 YES 或 NO，表示某个时刻农场是否是全连通的。

第一行输出最初的状态，第 $i$ 行（$2\le i\le N$）输出第 $i-1$ 个农场被关闭后的状态。

输入输出样例 #1

输入 #1

4 3
1 2
2 3
3 4
3
4
1
2

输出 #1

YES
NO
YES
YES

//转换+并查集
#include <bits/stdc++.h>
#define int long long 
#define PII pair<int,int>
#define ll long long 
#define endl '\n'
 
using namespace std;
 
const int N=2e5+10,M=5010;
 
int dot[N],used[N];
//记住，如果是无向图要开双倍的边； 因为这个wa了很多次 
int e[N*2],ne[N*2],h[N*2],idx;
int p[N];
bool st[N];
 
void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
 
int find(int x)
{
	if(x!=p[x])
	{
		p[x]=find(p[x]);
	}
	return p[x];
}
 
signed main()
{
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	
	int n,m;cin>>n>>m;
	memset(h,-1,sizeof h);
	
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;
		add(x,y);add(y,x);
	}
	
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
		cin>>dot[i];
	}
	
	int sum=1;//最开始集合中只有一个点；
	for(int i=n;i>=1;i--)
	{	
		//初始sum==0//sum++;当前一个点表示一个集合；
		int x=dot[i];used[x]=1;//标记为已经加入集合的点；
		
		int px=find(x);
		for(int j=h[x];j!=-1;j=ne[j])
		{
			int y=e[j];
			int py=find(y);
			//所以是p[py]=px;把所有的点连到新点中，
			//这样之前已经在集合中的点任一连到新点，那么就合并成功了
			//如果是p[px]=py的话，那么就是把新点连到已知的点中，
			//就会造成有些点没有连接到新点；答案错误；
			if(px!=py&&used[y])
			{
				p[py]=px; //如果是p[px]=py那么结果就错的；
				sum++;//sum--表示只有一个集合；
			}
		}
		//表示当前的集合中的点数，是否为这个；
		if(sum==n-i+1)st[i]=true; 
		//if(sum==1)st[i]=true;表示只有一个集合；
	}
	
	for(int i=1;i<=n;i++)
	{
		if(st[i])cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	return 0;
 } 

后记

作者：zty郑桐羽呀
联系方式：（企鹅 3782663736）
兄弟们给个赞呗
先 赞 后 看 养 成 习 惯