题目描述

🤢🤢🤢🤢并查集怎么这么。。。。。
一定要好好看题 一定要好好看题 。。。
1. 仓库一旦被关闭就再也不会开放使用了,所以后面问的整个农场是否全联通就不用管那些已经被关闭的仓库了。
2. 然后问题是每次关闭第i个仓库之前整个农场是否全联通。

根据上面第二个描述可知, 关闭最后一个仓库之前所有的仓库都被关闭了, 所以答案的最后一个点肯定是YES, 由此可知我们可以倒着想这个题, 初始将整个连通块看成空的,即所有仓库都被关闭了,然后将N个即将被关闭的农场的编号存下来, 先将第n个被关闭的点标记成打开状态,再将第n个点的状态标记成true(因为最后一个点肯定是YES)

于是乎我们从第n-1个点开始遍历判断当前这个点是否为true
遍历第n-1个点的邻边都有哪些点 然后将这些点都合并集合, 每次让k ++, 表示连了一条边, 最后判断当前点数是否等于边数减1, 如果是就为true 否则为false

可以用链表存储相邻的点

算法1

(并查集+链表存储)

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
int p[N];
int n, m, kk;
bool st[N]; //  判断当前这个农场是否开着
int f[N], ans[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++;
}

int find(int x)
{  
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d",&n, &m);

    for(int i = 1; i <= n; i ++ ) p[i] = i;  // 初始化每个集合

    for(int i = 1; i <= m; i ++ )   // 将相邻两个边连接起来
    {
        int u, v;
        scanf("%d%d",&u,&v);
        add(u, v);
        add(v, u);
    }

    for(int i = 1; i <= n; i  ++ ) scanf("%d", &f[i]); // 将每个要关闭的农场存到f数组中


    int cnt = 0;
    st[f[n]] = true; //说明第n个农场已经打开了
    ans[n] = 1; // 初始时, 只有一个农场所以为YES
    cnt ++;

    for(int i = n - 1; i >= 1; i -- )
    {
        cnt ++;
        st[f[i]] = true;  // 标记当前农场为打开状态
        for(int j = h[f[i]]; j != -1; j = ne[j])   // 找第i个农场相邻的农场(找临边)
        {
            int k = e[j]; // 找到第i个农场相邻农场的编号标记为k
            if(st[k]) // 如果相邻
            {
                int xx = find(f[i]), yy = find(k);
                if(xx != yy)
                {
                    kk ++;
                    p[xx] = yy;
                }
            }
        }
        if(kk == cnt - 1) ans[i] = 1;
        else ans[i] = 0;
    }

    for(int i = 1; i <= n; i ++ )
        if(ans[i]) printf("YES\n");
        else printf("NO\n");

    return 0;
}