简要题意

给定一张

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

个，报告任意一种合法的定向方案。

$1 \le n \le 100$ ， $0 \le m \le \frac{n(n-1)}{2}$
$1 \le u_i, v_i \le n$
$1 \le c_i \le n$
保证输入一定存在至少一种合法定向

设

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)

的定义。

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

$|R(v)| \leq |R(u)|$ ，即 $c_v \leq c_u$ 是必要的。
如果 $|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

强连通是必要的。

着手解决

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

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

对于 $c_u < c_v$ ， $u \gets v$ 是必要的
对于 $c_u > c_v$ ， $u \to v$ 是必要的

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

对于 $c_{u_i} = c_{v_i}$ ， $u_i$ 与 $v_i$ 强连通是必要的

注意到强连通是有传递性的，即，若

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.

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

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

将每条树边按父亲指向儿子定向
将每条返祖边按后代指向祖先定向

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

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

由求桥时的 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)|

序列始终唯一，而题目保证一定有解，因此必要也一定是充分的。

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

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

根据关键观察 2.，同一强连通分量内的 $R(i)$ 始终相等
将每个强连通分量缩点之后的图称为新图，新图始终唯一

由此每个点的可达点集

R(i)

序列始终唯一，因此

|R(i)|

序列始终唯一，证毕。

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

实现

伪代码

读入 $n, m$
读入 $(u_i, v_i)$
读入 $c_i$
对于每条边 $(u, v)$ $(u, v)$ :
- 如果 $c_u < c_v$ ，将此条边定向标记为 $u \gets v$
- 如果 $c_u > c_v$ ，将此条边定向标记为 $u \to v$
- 如果 $c_u = c_v$ ，将 $u, v$ 分别加入子图的点集，将 $(u, v)$ 加入子图的边集
对于子图的每个连通块
- 任取该连通块的一棵 DFS 生成树
- 将每条树边的定向标记为父亲指向儿子
- 将每条返祖边的定向标记为后代指向祖先
报告每条边的定向

真代码，C++14 标准

CPP

#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)

的空间，具体实现碍于篇幅不再赘述，洛谷有道例题。

一些启示

当从满足充分条件的角度不方便思考时，可以先想想满足必要条件，说不定满足足够多的必要条件后，条件就变充分了
~~可以从 ChatGPT 那里得知很多小名鼎鼎的定理~~

后记

感谢 ChatGPT-5.1 与 ChatGPT-5.1 Thinking 对本文严谨性的大力支持（未用其辅助生成本文文字）

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

题解：AT_arc111_d [ARC111D] Orientation

文章操作

简要题意

关键观察

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

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

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

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

着手解决

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

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

充分性呢？

实现

伪代码

真代码，C++14 标准

Extra：解决之后的思考

若不保证有解

一些启示

后记

相关推荐

评论

题解：AT_arc111_d [ARC111D] Orientation

文章操作

简要题意

关键观察

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

若 cu<cvc_u < c_vcu​<cv​：u←vu \gets vu←v 是必要的

若 cu>cvc_u > c_vcu​>cv​：u→vu \to vu→v 是必要的

若 cu=cvc_u = c_vcu​=cv​：强连通是必要的

着手解决

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

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

充分性呢？

实现

伪代码

真代码，C++14 标准

Extra：解决之后的思考

若不保证有解

一些启示

后记

相关推荐

评论

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

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

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

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