八中教室的灯加强版

发布时间：2024-12-13 00:24

在卧室安装柔和的壁灯，替代强烈的中央吊灯 #生活常识# #生活建议# #节能技巧# #节能照明#

原题网址：[https://begin.lydsy.com/JudgeOnline/problem.php?id=5971]

Description

八中一共有被用M条双向道路连接的N个教室(1<=N,M<=3000)。为了关闭整个八中，master wen 计划每一次关闭掉一个教室。当一个教室被关闭了，所有的连接到这个教室的道路都会被关闭，而且再也不能够被使用。master wen现在正感兴趣于知道在每一个时间（这里的“时间”指在每一次关闭教室之前的时间）时他的八中是否是“全
连通的”——也就是说从任意的一个开着的教室开始，能够到达另外的一个教室。注意自从某一个时间之后，可能整个八中都开始不会是“全连通的”。

Input

第一行给出数字N，M，代表有N个教室，M条边,1<=N,M<=200000接下来N行来用描述教室之间相连的情况接下来N行，每行给出一个数字，代表关闭了哪个教室的灯。

Output

输出N行，每行输出"YES"或"NO".
第一行输出最开始时整个八中是不是连通的
后面的N-1用来描述关闭某个教室的灯后，八中是不是连通的。

Sample Input

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

Sample Output

YES
NO
YES
YES

题目大意

给你n个点和m条边，依次删去一个点，求每种状态下是否连通。

题目解析

本题刚开始还以为是用暴力做法，但一看数据范围就不淡定了。不过各位也可以看一看弱化版[https://begin.lydsy.com/JudgeOnline/problem.php?id=5972]。
那么此题的正解应该是并查集：
但怎么用呢？这里要用一个小技巧：先把依次删去的点全部读进来，然后倒过来做。
定义一个sum，用来判断当前连通快的个数，若个数为1，则全部连通。
每读入一个点i，就先把sum++，然后搜索所有与i相连的点，若该点已经出现，且没有与i点连通，则可以做一次连通，并把sum-1。

程序实现

#include<bits/stdc++.h> using namespace std; bool flag[200010],ans[200010]; int n,m,tot,pre[400010],now[200010],ch[400010],f[200010],x,y,sum,kk[200010],k; inline void sb(int x,int y){pre[++tot]=now[x];now[x]=tot;ch[tot]=y;} int fa(int num) { int nu=num,nm; while(num!=f[num]) num=f[num]; while(nu!=f[nu]) nm=nu,nu=f[nu],f[nm]=num;//将树压得扁平，节省时间。 return num; }//合并 int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); sb(x,y),sb(y,x); } for(int i=1;i<=n;i++) scanf("%d",&kk[i]); for(int i=n;i>=1;i--) { sum++; k=kk[i]; flag[k]=true; for(int j=now[k];j;j=pre[j]) if(flag[ch[j]]&&fa(ch[j])!=fa(k)) f[fa(ch[j])]=f[fa(k)],sum--; if(sum==1) ans[i]=1; } for(int i=1; i<=n; i++) if(ans[i]==1)printf("YES\n"); else printf("NO\n"); return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142

请各位大神不吝赐教，如果入得了眼，请关注。在这里插入图片描述