在有向树中查找“最优根节点”？

Question

（这是从最近完成的编程竞赛中得出的）

给定一个具有N个节点和N-1条边的连通图G。（请注意，这意味着G形成一棵树。）

G的每条边都是有向的。（不一定朝向任何根）

对于G的每个顶点v，可以反转零个或多个边，使得从任何其他顶点w到v都存在一条有向路径。令实现此目的所需的最小可能边反转次数为f(v)。

我们如何通过线性或对数线性算法确定具有最小总f(v)的顶点子集（包括那些顶点的f(v)值）？

例如，考虑这些边缘的4个顶点图：

A<--B
C<--B
D<--B

f(A)的值为2，f(B)的值为3，f(C)的值为2，f(D)的值为2...

...因此所需输出结果为{A,C,D}和2

(请注意，我们只需要计算那些具有最小f(v)的顶点的f(v)值，而不是所有顶点)

代码:

以下是解决方案的代码:

int main()
{
    struct Edge
    {
        bool fwd;
        int dest;
    };

    int n;
    cin >> n;

    vector<vector<Edge>> V(n+1);

    rep(i, n-1)
    {
        int src, dest;
        scanf("%d %d", &src, &dest);

        V[src].push_back(Edge{true, dest});
        V[dest].push_back(Edge{false, src});
    }

    vector<int> F(n+1, -1);

    vector<bool> done(n+1, false);

    vector<int> todo;
    todo.push_back(1);
    done[1] = true;
    F[1] = 0;

    while (!todo.empty())
    {
        int next = todo.back();
        todo.pop_back();

        for (Edge e : V[next])
        {
            if (done[e.dest])
                continue;

            if (!e.fwd)
                F[1]++;
            done[e.dest] = true;
            todo.push_back(e.dest);
        }
    }

    todo.push_back(1);

    while (!todo.empty())
    {
        int next = todo.back();
        todo.pop_back();

        for (Edge e : V[next])
        {
            if (F[e.dest] != -1)
                continue;

            if (e.fwd)
                F[e.dest] = F[next] + 1;
            else
                F[e.dest] = F[next] - 1;

            todo.push_back(e.dest);
        }
    }

    int minf = INT_MAX;

    rep(i,1,n)
        chmin(minf, F[i]);

    cout << minf << endl;

    rep(i,1,n)
        if (F[i] == minf)
            cout << i << " ";
    cout << endl;

}

- Andrew Tomazos

Answer 1

我认为以下算法是正确的，并且它确实可以在线性时间内工作。

这个算法的动机如下。假设您已经知道某个单个节点v的f(v)值。现在，考虑任何与v相邻的节点u。如果我们想要计算f(u)的值，我们可以重复使用从f(v)中提取出来的一些信息来计算它。请注意，为了从图中的任意节点w到达u，必须发生以下两种情况之一：

1. 路径通过连接u和v的边。在这种情况下，我们从w到达u的方法是从w到达v，然后沿着从v到达u的边走。

2. 路径不通过连接u和v的边。在这种情况下，我们从w到达u所采用的方式与我们从w到达v所采用的方式完全相同，只是当我们到达u时停止。

这个观察结果很重要的原因是，它意味着如果我们知道从任何节点到v需要翻转的边的数量，我们就可以轻松地修改它，以得到从任何节点到u所需翻转的边的集合。具体而言，它将与以前相同的边集，只是我们希望将连接u和v的边定向，使其连接v到u而不是相反。

如果从u到v的边最初是定向的(u, v)，那么我们必须翻转所有正常的边，以使每个节点指向v，再加上一条边，使得v指向u。因此，f(u)=f(v)+1。否则，如果边最初是定向的(v, u)，则我们要翻转的边集与以前相同（指向v的所有内容），只是我们不会翻转边(v, u)。因此，f(u)=f(v)-1。

因此，一旦我们知道单个节点v的f值，我们就可以按以下方式计算每个相邻节点u的f值：

f(u) = f(v) + 1    if (u, v) is an edge.
f(u) = f(v) - 1    otherwise

这意味着我们可以按以下方式计算所有节点v的f(v)值：

1. 为任意选择的初始节点v计算f(v)。 2. 从v开始进行深度优先搜索。到达节点u时，使用上述逻辑计算其f分数。

现在只需计算某个初始节点v的f(v)值即可。为此，我们可以从v向外运行DFS。每当我们看到一个指向错误方向的边缘时，我们必须将其翻转。因此，在初始DFS期间发现的指向错误的边缘数量给出了f(v)的初始值。

因此，我们可以通过执行初始DFS以计算初始节点v的f(v)，然后执行二次DFS以计算每个其他节点u的f(u)，从而在O(n)时间内计算每个节点的f分数。然后，您可以循环遍历每个n个f分数以找到最小分数，然后再循环一次以找到所有具有该f分数的值。这些步骤中的每一步都需要O(n)时间，因此整个算法也需要O(n)时间。

希望这可以帮助您！这是一个很棒的问题！

- templatetypedef

---

+1 - 我发现了一个反例，我相当确定这种方法可行。 - dfb

这里的一个关键引理是，对于任何顶点v，存在唯一一组边反转来创建从所有其他顶点到v的路径。当我最初看问题时，我没有注意到这一点。 - Andrew Tomazos