posted on 2022-10-30 11:39:14 | under 题解 | source
problem
一个 \(n\) 个点 \(m\) 条边的有向图，\(q\) 次操作：
- 删除一条边，保证存在；
- 增加一条边，保证不存在；
- 删除一个点的所有入边；
- 将一个点曾经有的入边全部恢复。
每次操作后判断：
- 从任意一个节点出发，是否能走无限步；
- 对于任意一个节点，是否满足这个节点只有唯一的一条出边。
\(n,m,q\leq 10^6\)。
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
#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;
}