我的思路与卡壳点

我正在研究一个竞赛编程问题，给定一个有N 个顶点、M条边的混合图。某些边是固定的（有向），而其他边是自由的（无向），可以向任意方向定向。

通过对权值阈值进行二分搜索，并使用Tarjan的强连通分量（SCC）算法，我可以成功找到一个解存在的有效状态。也就是说，当我把所有自由边都视为双向边时，整个混合图形成一个强连通分量（SCC）。

现在，我在构造部分遇到困难：怎样实际给每条自由边指派一个方向，使最终的、完全有向的图仍然是一个SCC。

我的思路与卡壳点

我试图实现一个O(N + M) 的有向化过程，基于Robbins定理（以及Boesch和 Tindell对混合图的扩展）的DFS遍历。

核心想法是在遍历时同时使用固定边和自由边。当DFS遇到未定向的自由边时，应该沿着遍历路径强制其方向（s → v）。

然而，由于已有的有向边可能会强制出现在跨边或使树结构变得更复杂，我当前的实现会在某些拓扑结构上失败，因为回边/跨边被错误地排序处理。

我的问题

应如何构造DFS遍历或边的标记逻辑，才能正确处理混合图？

是否可以在一次DFS过程中就安全地在边定向？还是需要将定向与遍历解耦（例如使用 tin 在完全独立的无向遍历中生成的时间戳）？

任何洞见或对我的边界情况逻辑的修正都将不胜感激。

测试用例

下面给出一个很容易让人看出普通Robbins定理失效的案例。在这个案例中，最小阈值为3，因此只有权值不超过3 的边才是无向边。

4 5
1 2 3
1 3 5
1 4 1
2 3 3
4 3 4

这段代码只是我尝试的一个示例。我知道这段代码并非最优解。请尊重问题本身。我不是在问代码为什么错。我在问怎么去做。如果你真心想回答并帮助我，那么你应该理解这个问题，所以请不要对我描述问题的方式进行骚扰。

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

int main() {
    int n = 5; // number of nodes
    int m = 6; // number of edges
    int l = 10;

    // Graph adjacency list: {neighbor, edge_index}
    vector<vector<pair<int, int>>> ng(n);

    // Edge information
    vector<int> from(m), to(m), weight(m);

    /*
        Example graph
        edge 0: 0 -> 1
        edge 1: 1 -> 2
        edge 2: 2 -> 3
        edge 3: 3 -> 4
        edge 4: 4 -> 0
        edge 5: 1 -> 3
    */

    from = {0, 1, 2, 3, 4, 1};
    to   = {1, 2, 3, 4, 0, 3};
    weight = {5, 12, 4, 8, 15, 3};

    // Build graph
    for (int i = 0; i < m; i++) {
        ng[from[i]].push_back({to[i], i});
        ng[to[i]].push_back({from[i], i}); // undirected representation
    }

    string ans(m, '0');

    int timer = 0;

    vector<int> tin(n, -1);
    vector<bool> vis(n, false);
    vector<bool> used(m, false);

    auto dfsorient = [&](auto&& self, int s) -> void {
        vis[s] = true;
        tin[s] = timer++;

        for (auto edge : ng[s]) {
            int v = edge.first;
            int idx = edge.second;

            if (used[idx]) continue;
            used[idx] = true;

            // Fixed directed edge
            if (weight[idx] > l) {
                if (!vis[v]) {
                    self(self, v);
                }
                continue;
            }

            // Tree edge
            if (!vis[v]) {
                if (from[idx] == s)
                    ans[idx] = '0'; // keep direction
                else
                    ans[idx] = '1'; // reverse

                self(self, v);
            }
            // Back edge
            else {
                if (tin[v] < tin[s]) {
                    if (from[idx] == s)
                        ans[idx] = '0';
                    else
                        ans[idx] = '1';
                }
            }
        }
    };

    dfsorient(dfsorient, 0);

    cout << "Edge orientations:\n";
    for (int i = 0; i < m; i++) {
        cout << "Edge " << i << ": " << ans[i] << '\n';
    }

    return 0;
}

原始问题
https://www.mediafire.com/file/d4609k4b01dkkfm/utforditas.hu.pdf/file
在这里你可以下载匈牙利语版本。遗憾的是我没有其他语言的版本。

解决方案

这是一道著名的已解题，存在线性时间解法的题目，解法在论文 Chung, Garey, Tarjan: Strongly Connected Orientations of Mixed Multigraphs (1985) 中描述。我在这里给出一个不同的解释，但得到等价的结果。

设想这个蛮力做法：一直循环，找到一组能够构成有向环的边并将它们收缩成一个顶点，当再也不能用这种方式组成环时停止。若解存在，这个做法就能找到一个有效解，因为先前的环不会阻止后来的环被形成。它只需要高效地完成。

假设我们已经知道存在解。对某个根顶点运行DFS。在这种情况下有四种边的类型：

• 树边（从祖先指向后代的有向边，或无向边）
• 下行边（指向下方的有向边，但不属于DFS树）
• 回边（向上指向的有向边，或无向边）
• 跨边——一个关键的观察是，它们总是指向DFS早已访问过的顶点

对于每条树边，如果其较低端顶点的子树有一条回边离开子树，那么将这条树边定向向下也是可以的。当所有回边都向上定向时，这只会产生使用回边和树边构成的环。

剩下的树边怎么办？让我们按DFS的顺序来处理它们。对于边 u-v（上-下），假设如下的不变式成立：当这个过程结束时，DFS序中的所有前面的顶点肯定与根处于同一个SCC。

• 如果有一条跨边离开 v 的子树，那么对它定向为 u->v 也是可以的，因为在沿着从 u 到某条跨边的路径上，对树边重复对路径上的边进行处理时，它会与根的SCC构成一个耳状结构，从而形成一个环。
• 否则，能从 v 子树中指向外部的边只有 v->u。在初始图中，不可能还有来自 v 子树的其他双向边或离开子树的边，因此这是必要的。不变式以及前面的点告诉我们，这将从 u 到根的路径道出进入 v 子树的所有边（向下/跨边）。若没有退出边，不变式也告知要建立一个SCC，在包含于 v 的子树内递归执行这一过程时，需要从任一进入边向 v 构建一条路径，因为别无他法连接到根的SCC。换言之，当尝试为子树更深处的顶点“实现承诺”，假设对 v 已成立，那么对 v 也会成立。

最终，我们让所有顶点都满足该不变式，因此得到一个强连通分量。所有无向边都被定向为有向：在第一部分是所有回边和部分树边，在第二部分是剩余的树边。由于决定边的方向所需的全部信息都来自DFS构建树并对边进行分类后的初始状态，这个方法是线性时间可行的。我们可以用DFS计算每个子树中最早可达的顶点（在DFS顺序中）。

这个过程可用于检查是否存在解。如果它产生的结果不是一个SCC，那么就不存在解。