混合图中无向边定向以实现强连通的构造方法问询

给定包含N个顶点和M条边的混合图，其中部分边为**固定（有向）边，其余为自由（无向）**边可任意指定方向。已通过基于权重阈值的二分查找结合Tarjan的SCC算法确认：将所有自由边视为双向时，整个混合图是单个强连通分量（SCC）。当前卡在构造环节：如何为每条自由边指定方向，使最终的全向图仍为单个SCC。

思路与困境 #

尝试基于Robbins定理（及Boesch和Tindell对混合图的扩展），用DFS遍历实现O(N+M)的定向过程。核心思路是同时使用固定边和自由边进行遍历，遇到未定向的自由边时，将其方向设为遍历路径方向（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;
}

原问题说明 #

原问题为匈牙利语版本，暂无其他语言版本。

内容的提问来源于stack exchange，提问作者Kristóf Jenei