CF 1795G Removal Sequences

標籤： cf

给定一个无向图，每个点有一个权值 $a_i$，节点 $i$ 可以被删当且仅当 $i$ 的入度等于 $a_i$。要把整个图删光，存在许多删除序列，问有多少个二元组 $(i, j)$，使得在某个删除序列中，$i$ 比 $j$ 先删，而在另一个删除序列中，$j$ 比 $i$ 先删。保证存在至少一个删除序列。

求这样的二元组比较麻烦，考虑求其反面，即删除顺序确定的二元组 $(i, j)$。

首先，在删除的某个阶段，容易证明所有满足可删条件的点不相邻，换句话说，相邻的点被删的阶段一定不同。因为如果存在相邻，那么删除某一个，另一个入度减小，再也无法被删，与条件矛盾。

所以我们可以先 bfs 求出每个点被删除的阶段 $lvl_i$，那么对于相邻的两个点，$lvl$ 较小的一定在 $lvl$ 较大的之前被删。考虑给每条边定向，从 $lvl$ 较小的点指向较大的点，可以发现这个图一定是一个有向无环图。那么 $i$ 在 $j$ 之前被删就等价于可以从 $i$ 到达 $j$，问题就转变成统计有向无环图上的可达性统计。这个问题十分经典，令 $f(i, j)$ 表示第节点 $i$ 能否到达 $j$，则按照拓扑排序反向转移即可。

然而这样做是 $O(n^2)$ 的，无论内存还是时间上都无法通过。我们进行一些常数优化，将 $f(i)$ 定义成 uint64_t，并 64 个一组处理，假设当前是第 $k$ 组，那么 $i$ 可以到 $j (64k \le j < 64k + 64)$ 就表示成 $(f(i) \operatorname{rightshift} (j - 64k)) \operatorname{and} 1 = 1$。这样空间复杂度就是 $O(n)$ 的，每组的 $f$ 数组可以循环利用。而时间复杂度并没有优化，但常数优化了，可以通过此题。

代码很丑，推荐直接看题解。

struct graph
{
    vector<vector<int>> e;
    vector<int> indeg;
    graph(int n) : e(n), indeg(n) {}
};
 
struct directed_graph: public graph
{
    void add_edge(int u, int v)
    {
        // printf("add directed edge %d %d\n", u, v);
        e[u].emplace_back(v);
        indeg[v]++;
    }
    vector<int> sort()
    {
        int n = e.size();
        vector<int> res;
        res.reserve(n);
        std::queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                q.emplace(i);
            }
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            res.emplace_back(u);
            for (auto v : e[u]) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    q.emplace(v);
                }
            }
        }
        return res;
    }
    long long count_approach()
    {
        int n = e.size();
        long long res = 0;
        auto seq = sort();
        // std::reverse(seq.begin(), seq.end());
        for (int i = 0; i * 64 < n; i++) {
            vector<uint64_t> f(n);
            int l = i * 64, r = (i + 1) * 64;
            for (auto j : seq) {
                if (l <= j && j < r) f[j] |= 1ull << (j - l);
                res += std::popcount(f[j]);
                for (auto v : e[j]) {
                    f[v] |= f[j];
                }
            }
        }
        return res;
    }
};
 
struct origin_graph : public graph
{
    vector<int> a;
    origin_graph(int n) : graph(n), a(n) {}
    void read(int m)
    {
        int n = e.size();
        for (auto &i : a) cin >> i;
        for (int i = 0; i < m; i++)
        {
            int u, v;
            cin >> u >> v;
            add_edge(u - 1, v - 1);
        }
    }
    void add_edge(int u, int v)
    {
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        indeg[u]++;
        indeg[v]++;
    }
    directed_graph bfs()
    {
        int n = e.size();
        directed_graph res(n);
        vector<int> lvl(n);
        std::queue<std::pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == a[i]) {
                q.emplace(i, 0);
            }
        }
        while (!q.empty())
        {
            auto [u, l] = q.front();
            q.pop();
            lvl[u] = l;
            for (auto v : e[u]) {
                indeg[u]--;
                indeg[v]--;
                if (indeg[v] == a[v]) {
                    q.emplace(v, l + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (auto j : e[i]) {
                if (lvl[i] > lvl[j]) res.add_edge(i, j);
            }
        }
        return res;
    }
};
 
void solve()
{
    int n, m;
    cin >> n >> m;
    origin_graph g(n);
    g.read(m);
    auto ng = g.bfs();
    cout << (long long)n * (n - 1) / 2 + n - ng.count_approach() << endl;
}