简化下题意
有n个点 m条单向边 每条边有激活和失活两种状态，一共有4中操作
1.失活一条 u->v 的边
2.失活终点是 v 的边
3.激活 u->v 的边
4.激活终点是 v 的边
问你每次修改后 每个点的出度是否都为 1.
50分的做法就是暴力修改，对于 1操作和3操作 都是 可以 o(1)解决，对于 2操作和 4操作需要 o(n)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pir;
const int N = 5e5 + 5;
int out[N];
std::vector<int> g[N];
map<int, int>mp[N];
void solve()
{
int n, m;
cin >> n >> m;
int cnt = 0;
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
g[v].push_back(u);
mp[v][u] = 1;
out[u]++;
if(out[u] == 1)cnt++;
else if(out[u] == 2)cnt--;
}
int q;
cin >> q;
while(q--)
{
int op, u, v;
cin >> op;
if(op == 1)
{
cin >> u >> v;
mp[v][u] = 0;
out[u]--;
if(out[u] == 0)cnt--;
else if(out[u] == 1)cnt++;
}
else if(op == 2)
{
cin >> u;
for(int v : g[u])
{
if(mp[u][v])
{
out[v]--;
if(out[v] == 0)cnt--;
else if(out[v] == 1)cnt++;
mp[u][v] = 0;
}
}
}
else if(op == 3)
{
cin >> u >> v;
mp[v][u] = 1;
out[u]++;
if(out[u] == 1)cnt++;
else if(out[u] == 2)cnt--;
}
else
{
cin >> u;
for(int v : g[u])
{
if(mp[u][v] == 0)
{
out[v]++;
if(out[v] == 1)cnt++;
else if(out[v] == 2)cnt--;
mp[u][v] = 1;
}
}
}
if(cnt == n)cout << "YES\n";
else cout << "NO\n";
}
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
solve();
}
发现如果维护入度，那么对于4个操作都复杂度都是 o(1).
当符合每个点的出度都为 1 时，那么出度 总和就是 n,入度总和也是 n。
入度为 n 只是符合题目的一个 必要条件。
本题就是使用随机化使得这个必要条件无限接近充分必要条件。
具体做法是 对每个点i赋一个随机的权值 w[i].
对于每个点u的入度和就是
现在只要保证 $$(\sum_{i=1}^n r[i]) == (\sum_{i=1}^n w[i])$$
既能保证当前每个点的出度为 1
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pir;
const int N = 5e5 + 5;
void solve()
{
int n, m;
cin >> n >> m;
std::mt19937 rnd(time(0));
std::vector<ll> w(n + 1);
ll sum = 0;
for(int i = 1; i <= n; i++)
{
w[i] = rnd();
sum += w[i];
}
std::vector<ll> r(n + 1), g(n + 1);
ll tot = 0;
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
r[v] += w[u];
tot += w[u];
}
for(int i = 1; i <= n; i++)g[i] = r[i];
int q;
cin >> q;
while(q--)
{
int op, u, v;
cin >> op;
if(op == 1)
{
cin >> u >> v;
r[v] -= w[u];
tot -= w[u];
}
else if(op == 2)
{
cin >> u;
tot -= r[u];
r[u] = 0;
}
else if(op == 3)
{
cin >> u >> v;
r[v] += w[u];
tot += w[u];
}
else
{
cin >> u;
tot += g[u] - r[u];
r[u] = g[u];
}
if(tot == sum)cout << "YES\n";
else cout << "NO\n";
}
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
solve();
}
/*
*/