https://www.luogu.com.cn/problem/P6121

[USACO16OPEN] Closing the Farm G

题目背景

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

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

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

样例 #1

样例输入 #1

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

样例输出 #1

YES
NO
YES
YES

提示

This corresponds to the string “(())()”.

As discussed above.

输出答案要mod12345678910

反向建边，就是正序删点（边）变成反向加边（点）

判断是否联通自然想到并查集。

但不过此题是要在图中删点，这一点用并查集来完成比较困难。

那何为并查集？当然有两大功能：合并和查找。那我们不妨把删点操作转换成合并。
比如

4 3
1 2
2 3
3 4
3
4
1

我们一共有4个点，然后依次要删点3、4、1、2，那么我们可以假设原本图中一个点都没有，然后依次加点2、1、4、3，并把与它相关的点连起来，查找集合的个数，如果只有一个集合，则当前全联通。

const int N = 200010;
int a[N], vis[N], f[N];
int e[N * 2], ne[N * 2], h[N], idx;
int ans[N];
void add(int a, int b)
{
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}
int find(int x)
{
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++) cin >> a[i], vis[a[i]] = 1;
    int sum = 0;
    for (int i = n; i >= 1; i--)
    {
        sum++;
        int u = a[i];
        for (int j = h[u]; j; j = ne[j])
        {
            int k = e[j];
            if (find(k) != find(u) && !vis[k]) f[find(k)] = find(u), sum--;
        }
        vis[u] = 0;
        ans[i] = sum;
    }
    for (int i = 1; i <= n; i++)
    {
        if (ans[i] == 1) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}