题解 P8819【[CSP-S 2022] 星战】
yukimianyan
·
·
题解
problem
一个 n 个点 m 条边的有向图，q 次操作：
- 删除一条边，保证存在；
- 增加一条边，保证不存在；
- 删除一个点的所有入边；
- 将一个点曾经有的入边全部恢复。
每次操作后判断：
- 从任意一个节点出发，是否能走无限步；
- 对于任意一个节点，是否满足这个节点只有唯一的一条出边。
## solution
首先我们发现“从任意一个节点出发，是否能走无限步”是假的。
>如果第二条“对于任意一个节点，它只有唯一的一条出边”成立，那么从一个点出发，可以沿着它的出边一直走，不可能走到一个没有出边的点。
所以我们只需要判断，$\forall out_i=1$。相当于判断：
- 若 $E$ 是当前存在的边集，则 $|E|=n$。（这个点可以保证 $\oplus$ 不会受到 $>1$ 条边的影响）
- 对于每个点 $u$，都存在 $(u\to v)\in E$。
这里对于第二个点的判断方法是 hash。给每个点赋权值 $w_i$ 后，动态维护 $\sum_{(u\to v)\in E}w_u$ 或者 $\oplus_{(u\to v)\in E}w_u$，判断每次操作后是否有 $\sum_{(u\to v)\in E}w_u=\sum_u w_u$ 即可。
观察到 $+,\oplus$ 具有可减性，那么我们可以动态维护点 $u$ 的所有入边的 hash 值 $h_u$，进行 2,4 操作时将维护的 hash 值减掉 / 加上即可。具体实现建议看代码。
## code
```cpp
#include <cstdio>
#include <cstring>
#include <random>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
template<int N,int M,class T=int> struct graph{
int head[N+10],nxt[M*2+10],cnt;
struct edge{
int u,v;T w;
edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
} e[M*2+10];
graph(){memset(head,cnt=0,sizeof head);}
edge operator[](int i){return e[i];}
void add(int u,int v,T w=0){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
void link(int u,int v,T w=0){add(u,v,w),add(v,u,w);}
};
int n,m,q,tot;
mt19937_64 rng(time(0));
ULL w[500010],sum,h[500010],inn[500010],tar[500010],ind[500010];
int main(){
// #ifdef LOCAL
// freopen("galaxy4.in","r",stdin);
// freopen("galaxy4.out","w",stdout);
// #endif
for(int i=1;i<=5e5;i++) w[i]=rng();
scanf("%d%d",&n,&m),tot=m;
for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),sum^=w[u],h[v]^=w[u],inn[v]++;
memcpy(tar,h,sizeof tar);
memcpy(ind,inn,sizeof ind);
for(int i=1;i<=n;i++) tar[0]^=w[i];
scanf("%d",&q);
for(int op,u,v;q--;){
scanf("%d%d",&op,&u);
if(op==1) scanf("%d",&v),h[v]^=w[u],sum^=w[u],inn[v]--,tot--;
else if(op==3) scanf("%d",&v),h[v]^=w[u],sum^=w[u],inn[v]++,tot++;
else if(op==2){
tot-=inn[u],sum^=h[u];
inn[u]=h[u]=0;
tot+=inn[u],sum^=h[u];
}else if(op==4){
tot-=inn[u],sum^=h[u];
inn[u]=ind[u],h[u]=tar[u];
tot+=inn[u],sum^=h[u];
}
puts(tot==n&&sum==tar[0]?"YES":"NO");
}
return 0;
}
```