P3144 关闭农场并查集反向

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

这个农场一共有被用M条双向道路连接的N个谷仓(1<=N,M<=3000)。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

YES
NO
YES
YES

题意：给出n个点和m条无向边每次去掉一个点查看联通块是否为1

遵循先判断输出然后去掉一个点的原则

并查集find1一定要优化一开始就因为这个超时

因为并查集没有拆掉的操作所以要倒着来每次加上一个点（比如拆到最后一个点的时候是一个点倒着来补上第一个点的时候也是那一个点所以是一样的）
因为奇特的读入输出模式其实就是为了倒着来所准备的

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
///////////////////////////////////
#define inf 0x3f3f3f3f
#define N 3000+5

int n,m;
int x[N],y[N];
int in[N];
int f[N];
int node[N];
int ans[N];
int find1(int x)
{
    return f[x]==x?x:(f[x]=find1(f[x]) );

}
void union1(int a,int b)
{
    int x=find1(a);
    int y=find1(b);
    if(x!=y)
        f[x]=y;
}

int main()
{
    RII(n,m);
    rep(i,1,n)
    f[i]=i;
    rep(i,1,m)
    {
        RII(x[i],y[i]);
    }
    rep(i,1,n)
    {
        RI(node[i]);
        in[node[i]]=0;
    }

    repp(i,n,1)
    {
        in[ node[i] ]=1;
        rep(j,1,m)
        if( in[ x[j] ]&&in[ y[j] ] )
            union1( x[j],y[j] );
            
        rep(j,1,n)//遍历n查看有几个联通块
        if(in[j]&&f[j]==j)
            ans[i]++;
    }
    rep(i,1,n)
    if(ans[i]==1)
        printf("YES
");
    else
        printf("NO
");
   return 0;
}

View Code

P3144 关闭农场 并查集 反向

输入输出样例

P3144 关闭农场并查集反向