在有向树图中找到"最佳根"？

Question

(这来自最近完成的编程竞赛)

给出G,一个具有N个节点和N-1个边的连通图.

(请注意,这意味着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;

}

Answer 1

我认为以下算法正常工作,它肯定在线性时间内工作.

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

1. 那条路径经过连接u和v的边缘.在这种情况下,我们从w到u的方式是从w到v,然后是从v到u的边缘.
2. 那条路径没有经过连接u和v的边缘.在这种情况下,我们从w到u的方式与从w到v的方式完全相同,只是我们一到达你就停止了.

这个观察很重要的原因是它意味着如果我们知道我们要从任何节点转到v的边的数量,我们可以很容易地修改它以获得我们要翻转的边集.你的任何节点.具体来说,它将与以前一样是一组边缘,除了我们想要指向连接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(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开始执行DFS.当到达节点u时,使用上述逻辑计算其f分数.

剩下要做的就是为某个初始节点计算f(v).为此,我们可以从v向外运行DFS.每当我们看到边缘指向错误的方向时,我们就必须翻转它.因此,f(v)的初始值由我们在初始DFS期间找到的错误指向边的数量给出.

因此,我们可以通过初始DFS计算初始节点的f(v),然后为每个其他节点u计算f(u)的辅助DFS,在O(n)时间内计算每个节点的f分数.然后,您可以循环遍历每个n f分数以找到最小分数,然后再循环一次以查找具有该f分数的所有值.这些步骤中的每一步都花费O(n)时间,因此整个算法也花费O(n)时间.

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