关闭农场

【问题描述】

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

　　这个农场一共有被用 M 条双向道路连接的 N 个谷仓。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。

当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

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

【输入格式】

　　第 1 行是 N 和 M ；
　　接下来的 M 行，每行包含两个整数，表示一条双向道路连接的的两个谷仓。
　　最后的 N 行，每行是一个整数，表示本次关闭的谷仓。

【输出格式】

　　输出 N 行，其中第 i 行输出，如果关闭谷仓 i 全连通，则输出 Yes，否则输出 No。

【输入输出样例】

　 Input
4 3
1 2
2 3
3 4
3
4
1
2
　Output
YES
NO
YES
YES

【数据说明】

　　对于 100% 的数据 1≤N,M≤3000。

思路：

这里将谷仓一个个关闭，但是我们可以反其道而行之，将谷仓的开放顺序储存下来，然后，逆序进行判断，将要删去的点一个个加进来，遍历其所连的边上的点。

如果所连的点已经被加入了（开放了），同时两个点不属于同一个集合，我们就把两个集合合并，同时用tot储存集合内点的数量,当tot=n-i时就说明这个图是全联通的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
int n,m;
vector<int> e[maxn];
int vis[maxn];
int k[maxn];
int pa[maxn];
bool ans[maxn];
void makeset()
{
    for(int i=1;i<=n;i++)
    {
        pa[i]=i;
    }
}
int Find(int x)
{
    int r=x;
    while(pa[r]!=r)
    r=pa[r];
    return r;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);

    }
    for(int i=1;i<=n;i++)
    {
        cin>>k[i];
    }
    makeset();
    int tot=0;
    for(int i=n;i>=1;i--)
    {
        vis[k[i]]=1;
        int x=Find(k[i]);

        for(int j=0;j<e[x].size();j++)
        if(vis[e[x][j]]==1)
        {
            int y=Find(e[x][j]);
            if(x!=y)
            {
                tot++;
                pa[y]=x;
            }
        }
        if(tot==n-i)
        ans[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==1)
        printf("YES\n");
        else
        printf("NO\n");
    }
    return 0;
}