¿Encontrando las "mejores raíces" en un gráfico de árbol dirigido?

Question

(Esto se deriva de un concurso de programación recientemente completado)

Se le ha asignado G, un gráfico conectado con N nodos y N-1 bordes.

(Observe que esto implica G forma un árbol.)

Cada borde de G se dirige. (no necesariamente hacia arriba a cualquier raíz)

Para cada vértice v de G es posible invertir cero o más bordes de manera que haya una ruta dirigida desde cada vértice w a v. Deje el mínimo número posible de inversiones en los bordes para lograr esto, f (v).

¿Con qué algoritmo lineal o loglineal podemos determinar el subconjunto de vértices que tienen el mínimo global f (v) (incluido el valor de f (v) de esos vértices)?

Por ejemplo considerar el gráfico 4 vértice con estos bordes:

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

El valor de f (A) = 2, f (B) = 3, f (C) = 2 y f (D) = 2 ...

..Así por lo tanto, la salida deseada es {a, C, D} y 2

(en cuenta que sólo necesitamos calcular el f (v) de vértices que tienen una f mínima (v) - no todos ellos)

Código:

Para la posteridad aquí está el código de la solución:

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

Creo que el siguiente algoritmo funciona correctamente, y ciertamente funciona en tiempo lineal.

La motivación para este algoritmo es la siguiente. Supongamos que ya conoce el valor de f (v) para un solo nodo v. Ahora, considere cualquier nodo u adyacente a v. Si queremos calcular el valor de f (u), podemos reutilizar parte de la información de f (v) para calcularlo. Tenga en cuenta que con el fin de obtener de cualquier nodo w en el gráfico de u, uno de los dos casos debe suceder:

1. Ese camino pasa por el borde de conexión u y v En ese caso, la forma en que obtenemos de. w u es ir de w a v, luego seguir el borde de v a u.
2. Esa ruta no pasa por el borde que conecta uy v. En ese caso, la forma en que obtenemos de w a u es exactamente la misma que obtuvimos de w a v, excepto que paramos tan pronto como llegar a ti.

La razón por la que esta observación es importante es porque significa que si conocemos el número de aristas que volteamos para pasar de cualquier nodo a v, podemos modificarlo fácilmente para obtener el conjunto de bordes que daría la vuelta para llegar desde cualquier nodo hacia ti. Específicamente, va a tener el mismo conjunto de aristas que antes, excepto que queremos dirigir el borde que conecta u y v para que se conecte v con u en lugar de hacerlo al revés.

Si el borde de u a v se dirige inicialmente (u, v), entonces tenemos que voltear todos los bordes normales que volteamos para que cada nodo apunte a v, más un borde más para que v se apunte hacia atrás . Entonces f (u) = f (v) + 1.De lo contrario, si el borde se dirige originalmente (v, u), entonces el conjunto de bordes que voltearíamos sería el mismo que antes (apuntando todo a v), excepto que no daríamos la vuelta al borde (v, u) Por lo tanto f (u) = f (v) - 1.

En consecuencia, una vez que sabemos el valor de f para un solo nodo v, podemos calcular que para cada nodo adyacente u como sigue:

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

Esto significa que podemos calcular f (v) para todos los nodos v como sigue:

1. Compute (v) f por algún nodo v inicial, elegido arbitrariamente.
2. Realice un DFS comenzando desde v. Al llegar a un nodo u, calcule su puntaje f usando la lógica anterior.

Todo lo que queda por hacer es calcular f (v) para un nodo inicial. Para hacer esto, podemos ejecutar un DFS desde v hacia afuera. Cada vez que vemos un borde apuntando hacia el lado equivocado, tenemos que voltearlo. Por lo tanto, el valor inicial de f (v) está dado por el número de bordes de puntería incorrecta que encontramos durante el DFS inicial.

Por lo tanto, podemos calcular el puntaje f para cada nodo en O (n) tiempo haciendo un DFS inicial para calcular f (v) para el nodo inicial, luego un DFS secundario para calcular f (u) para cada otro nodo tú A continuación, puede for-loop sobre cada uno de los n-puntajes para encontrar el puntaje mínimo, luego hacer un ciclo más para encontrar todos los valores con ese puntaje-f. Cada uno de estos pasos toma O (n) tiempo, por lo que el algoritmo general también toma tiempo O (n).

Espero que esto ayude! ¡Este fue un gran problema!