题解：AT_arc111_d [ARC111D] Orientation

· · 题解

简要题意

给定一张 n 个点 m 条边的简单无向图与一个正整数序列 c_1,c_2, \dots,c_n。

目标是将每条无向边 (u_i, v_i) 定向成 u_i \to v_i 或 v_i \to u_i，得到一张有向图，使得对于每个点 i，从 i 出发可达的点（包括 i 自己）恰好有 c_i 个，报告任意一种合法的定向方案。

设 R(i) 为点 i 可达的点集（包括 i 自己），题目给出的 c_i 即是对 |R(i)| 的要求。

关键观察

假设有一条有向边 u \to v，一定有 R(v) \subseteq R(u)

证明：\forall \ x \in R(v)，都可以走 u \to v \leadsto x，所以一定有 x \in R(u)，符合 R(v) \subseteq R(u) 的定义。

有了这个观察，可以立刻得到：

  2. 如果 |R(v)| = |R(u)|，即 c_v = c_u 是必要的，又因为 R(v) \subseteq R(u)，只能是 R(v) = R(u)。

设有一条无向边 \{u, v\}：

若 c_u < c_v：u \gets v 是必要的

反证，设 u \to v，根据 1.，要求 c_v \leq c_u，与 c_u < c_v 矛盾，因此 u \gets v 是必要的。

若 c_u > c_v：u \to v 是必要的

证明同上。

若 c_u = c_v：强连通是必要的

假设是 u \to v，根据 2.，要求 R(v) = R(u)。由于一定有 u \in R(u)，因此 u \in R(v)，即 u 与 v 强连通。

假设 u \gets v 会获得一样的结果。因此，只能得到 u 与 v 强连通是必要的。

着手解决

当问题似乎无法变得更简单时，或许可以试着开始着手解决了。

先总结一下目前拥有的观察：

直接按必要性定向，这部分必要性自然满足。

注意到强连通是有传递性的，即，若 u 与 v 强连通，v 与 w 强连通，则 u 与 w 强连通。

因此考虑构建一张子图，所有满足 c_{u_i} = c_{v_i} 的 (u_i, v_i) 为元素组成的集合为该子图的边集，每条边的两个顶点分别为元素组成的集合为该子图的点集。

还需满足的必要条件：为这张子图的每个极大连通子图（连通块）的每条边定向，使得每个极大连通子图都是强连通图。

为一张无向图的每条边定向，使得其强连通

小名鼎鼎的 Robbins 定理指出：存在方案的充要条件为：此图无桥（割边）。

In graph theory, Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

由于题目保证有解，且此为必要条件，因此一定存在方案，即子图的每个极大连通子图一定不存在桥。

而定理附上的构造，这是我们所关心的：

A strong orientation of a given bridgeless undirected graph may be found in linear time by performing a depth-first search of the graph, orienting all edges in the depth-first search tree away from the tree root, and orienting all the remaining edges (which must necessarily connect an ancestor and a descendant in the depth-first search tree) from the descendant to the ancestor.

  1. 任取此图的任意一棵 DFS 生成树

由于是无向图的 DFS 生成树，因此只存在树边与返祖边。

  1. 将每条树边按父亲指向儿子定向

  2. 将每条返祖边按后代指向祖先定向

流程结束，若此图无桥，此图一定强连通。

比具体的、严谨的证明更易懂的，本质的观察是：

由求桥时的 tarjan 算法：

图无桥 \iff 对于图的 DFS 树上每个非根结点 u，都有 \text{low}_u < \text{dfn}_u

由求强连通分量时的 tarjan 算法：

对于图的 DFS 树上每个非根结点 u，都有 \text{low}_u < \text{dfn}_u \iff 没有任何一棵非根结点 u 的子树单独形成一个强连通分量

又因为对于根 r 一定有 \text{low}_r = \text{dfn}_r，因此此图只有一个强连通分量，即整张图，即此图强连通。

充分性呢？

有没有发现，目前为止都只研究了必要性，即在题目给定的信息下，有哪些条件是必须满足的，若不满足，一定与给定的信息矛盾。

但充分性该如何保证？即，还需要满足哪些条件，才能符合题目的信息？即满足 \forall i \in \{1,2,\dots,n\}, \ |R(i)| = c_i。

实际上，已经充分了。因为在满足这些必要条件的前提下，所有合法的定向，计算出的 |R(i)| 序列始终唯一，而题目保证一定有解，因此必要也一定是充分的。

非严谨证明，大概的观察：

在必要条件的前提下，无论怎么定向：

由此每个点的可达点集 R(i) 序列始终唯一，因此 |R(i)| 序列始终唯一，证毕。

至此，思路部分完结散花！

实现

伪代码

真代码，C++14 标准

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

constexpr int N = 100 + 1, M = 100 * (100 - 1);

int u[M], v[M], c[N];
vector<pair<int, int>> adj[N];
bitset<N> vis;
bitset<M> way;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u[i] >> v[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }
    for (int i = 0; i < m; ++i) if (c[u[i]] == c[v[i]]) {
        adj[u[i]].emplace_back(v[i], i << 1);
        adj[v[i]].emplace_back(u[i], i << 1 | 1);
    }

    auto dfs = [](const auto &self, int u) -> void {
        vis[u] = true;
        for (const auto &i : adj[u]) {
            const int &v = i.first, &eid = i.second;
            if (way[eid ^ 1]) {
                continue;//防止一条无向返祖边被标记两次
            }
            way[eid] = true;
            if (!vis[v]) {
                self(self, v);
            }
        }
    };
    for (int i = 1; i <= n; ++i) if (!vis[i]) {
        dfs(dfs, i);
    }

    for (int i = 0; i < m; ++i) {
        if (c[u[i]] == c[v[i]]) {
            cout << (way[i << 1] ? "->\n" : "<-\n");
        } else {
            cout << (c[u[i]] < c[v[i]] ? "<-\n" : "->\n");
        }
    }
    return 0;
}

时空复杂度：O(n + m)。

Extra：解决之后的思考

若不保证有解

若题目不保证一定有解，如何判断是否存在解？

在着手解决的充分性呢？ 一节中，可以得知，在满足着手解决的所有必要条件后，对于所有合法的定向，R(i) 序列始终唯一。

因此可以在定向完所有边后的图中，计算 |R(i)| 序列，与 c_i 序列对比即可。

朴素实现的时空复杂度为 O(n + m + n(n + m))。缩点后使用 bitset 加速 dag 上的可达性统计可以做到 O(n + m + \frac{n(n + m)}{w}) 的时间，O(n^2 + m) 的空间，具体实现碍于篇幅不再赘述，洛谷有道例题。

一些启示

后记

由于更新一篇已经被洛谷全站推荐的文章需要重新审核，审核期间文章将被撤下全站推荐；因此若有一些小勘误或补充，会优先在博客园同步发布的本文做出更新，视重要程度在洛谷后更新。欢迎在任意一个平台的本文评论区指出错误和学术讨论！感谢能看到这里的大家！