题解：AT_abc420_e [ABC420E] Reachability Query

· · 题解

终于能切第五题了！发个题解纪念纪念！

题意比较明了，这里不再过多复述。

思路 1.0

直接按照题目模拟。

对于操作一，我们连接给定的两个点。

对于操作二，我们切换给定的点的颜色。

对于操作三，我们去搜索给定的点连出去的点有没有黑色节点。

时间复杂度：O(qn)。

成功 TLE。

很明显，上面的方法不够快，我们要考虑一种更快的方法。

思路 2.0

首先，点与点之间只会有连接操作，不会有删边操作。

这很容易让我们想到并查集。

我们先用两个数组来存储并查集和并查集的大小。

然后，我们再用两个数组分别存储 i 节点的颜色和以 i 为根时的黑色节点个数。

那么，接下来的操作就很好办了。

对于操作一，我们找到两个节点的根，如果两个根节点不一样的话，我们合并两个根所在的集合，然后两个黑色节点的数量要加起来，并更新集合大小。

对于操作二，我们找到给定节点的根，然后，如果给定节点颜色从白变成黑，则所在集合里的黑色节点数量要加一，否则减一。

对于操作三，我们找到给定节点的根节点，如果当前这个集合里黑色节点的个数不为 0，则一定可以到达一个黑色节点，否则一定不能。

代码

#include<bits/stdc++.h>
using namespace std;
int n,t,a[200010],b[200010],c[200010],d[200010];
int dfs(int u){
    while (a[u] != u) a[u] = a[a[u]],u = a[u];
    return u;
}
int main(){
    cin >> n >> t;
    for (int i = 1;i <= n;i++) a[i] = i,b[i] = 1,c[i] = d[i] = 0;
    while (t--){
        int op;
        cin >> op;
        if (op == 1){
            int u,v;
            cin >> u >> v;
            int x = dfs(u),y = dfs(v);
            if (x != y){
                if (b[x] > b[y]) a[y] = x,b[x] += b[y],d[x] += d[y];
                else a[x] = y,b[y] += b[x],d[y] += d[x];
            }
        } else if (op == 2){
            int v;
            cin >> v;
            int x = dfs(v);
            if (c[v] == 0) c[v] = 1,d[x]++;
            else c[v] = 0,d[x]--;
        } else if (op == 3){
            int v;
            cin >> v;
            int x = dfs(v);
            if (d[x] > 0) printf("Yes\n");
            else printf("No\n");
        }
    }
}