打卡信奥刷题（2993）用C++实现信奥题 P6121 [USACO16OPEN] Closing the Farm G

P6121 [USACO16OPEN] Closing the Farm G

题目背景

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

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

第一行输出最初的状态，第i ii行（2 ≤ i ≤ N 2 \leq i \leq N2≤i≤N）输出第i − 1 i-1i−1个农场被关闭后的状态。

输入输出样例 #1

输入 #1

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

输出 #1

YES NO YES YES

C++实现

#include<bits/stdc++.h>usingnamespacestd;vector<int>e[200005];intf[200005];intm,n;intfind(intx){if(f[x]==x)returnx;returnf[x]=find(f[x]);}intmerge(intx,inty){if(find(x)==find(y))return0;f[find(x)]=find(y);return1;}//标准的并查集操作intl,r;intdel[200005];//删除的点intsum;//联通块数量boolok[200005];//是否全部连通intmain(){scanf("%d%d",&n,&m);for(registerinti=1;i<=m;i++){scanf("%d%d",&l,&r);e[l].push_back(r);e[r].push_back(l);}//vector存储边，是双向存储for(registerinti=1;i<=n;i++)scanf("%d",&del[i]);for(registerinti=n;i>=1;i--){//倒序枚举删除点intx=del[i];f[x]=x;//初始化 ，如果在之前全部初始化了，不好判断是否枚举过++sum;//加一个点，联通块数量++，之后再进行操作for(vector<int>::iterator it=e[x].begin();it!=e[x].end();it++){inty=*it;if(!f[y])continue;//如果还没有加这个点，因为之前的初始化sum-=merge(x,y);//如果可以连通，合并之后联通块--}if(sum<=1)ok[i]=true;//联通块为1的话，说明全部连通}for(registerinti=1;i<=n;i++){//正序输出if(ok[i]==true)puts("YES");elseputs("NO");}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容