【P8819 [CSP-S 2022]】 星战 题解（图论 + 哈希）

图论 + 哈希。

Link.

因为实在是太妙了所以写个题解。

Solution

• 因为每个点的出度都为 \(1\)，所以从任意一点出发永远可以走下去，故每次只需判断每个点度数是否为 \(1\) 即可。

• 然后一三操作显然直接 \(O(1)\) 维护，\(50\ pts\)。

• 考虑二四操作。每次操作显然对点 \(u\) 的出度没有影响，但是对边的起点 \(v\) 的出度有影响。考虑如何把操作转化到对 \(u\) 的修改上来。

• 发现可以维护一个点的入度。如果不考虑反攻时刻的判断，四个操作在入度上的修改都能做到 \(O(1)\)。

• 根据入度 = 出度，反攻时刻的判断可以变为所有节点的入度值等于 \(n\)。但是这样无法保证每个节点的出度都是 \(1\)。

• 考虑优化一下入度的计算，实现 \(O(1)\) 判断所有节点的出度一定都为 \(1\)。结合起来考虑，发现如果使用哈希的思想，给每个节点随机权值 \(w_i\)，定义一个节点的入度为所有边起点的权值和，那么如果 \(\sum r_i=\sum w_i\)，则能保证每个节点都有一条出边指向某个节点。

• 解题重点在于转化与哈希思想。如果想到第一条和哈希，此题基本迎刃而解。

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 5e5 + 5;
int n, m, q;
int tot, r[maxn], w[maxn], g[maxn];

mt19937 rng(time(0));

signed main(){
	scanf("%lld%lld", &n, &m);
	rep(i, 1, n) w[i] = rng(), tot += w[i];
	int rec = 0;
	while(m--){ int u, v; scanf("%lld%lld", &u, &v);
		g[v] = (r[v] += w[u]), rec += w[u];
	}
	scanf("%lld", &q);
	while(q--){
		int t; scanf("%lld", &t);
		if(t == 1){ int u, v; scanf("%lld%lld", &u, &v);
			r[v] -= w[u], rec -= w[u];
		} else if(t == 2){ int v; scanf("%lld", &v);
			rec -= r[v], r[v] = 0;
		} else if(t == 3){ int u, v; scanf("%lld%lld", &u, &v);
			r[v] += w[u], rec += w[u];
		} else{ int v; scanf("%lld", &v);
			rec += g[v] - r[v], r[v] = g[v];
		} if(rec == tot) printf("YES\n"); else printf("NO\n");
	}
	return 0;
}

Thanks for reading.