Dado un árbol dirigido con V vértices y V-1 aristas, debemos elegir dicha raíz (de Nodes dados desde donde podemos llegar a todos los demás Nodes) con un número mínimo de inversión de aristas.
Ejemplos:
In above tree, if we choose node 3 as our root then we need to reverse minimum number of 3 edges to reach every other node, changed tree is shown on the right side.
Podemos resolver este problema usando DFS . comenzamos dfs en cualquier Node aleatorio del árbol dado y en cada Node almacenamos su distancia desde el Node inicial asumiendo que todos los bordes no están dirigidos y también almacenamos el número de bordes que deben invertirse en la ruta desde el Node inicial hasta el Node actual, denotemos tales bordes como bordes posteriores, por lo que los bordes posteriores son aquellos que apuntan hacia el Node en un camino. Con este dfs, también calculamos el número total de inversiones de borde en el árbol. Después de este cálculo, en cada Node podemos calcular el ‘número de inversión de borde para llegar a todos los demás Nodes’ de la siguiente manera,
Sea R el número total de reversiones en el árbol cuando se elige algún Node como Node de inicio para dfs, entonces si queremos llegar a todos los demás Nodes desde el Node i, debemos revertir todos los bordes posteriores desde el Node de ruta i hasta el Node de inicio y también necesitamos invierta todos los demás bordes posteriores que no sean el Node i a la ruta del Node inicial. La primera parte será (distancia del Node i desde el Node inicial – los bordes posteriores cuentan en el Node i) porque queremos invertir los bordes en la ruta desde el Node i hasta el Node inicial, serán los bordes totales (es decir, la distancia) menos los bordes posteriores desde el Node inicial hasta el Node inicial. Node i (es decir, cuenta de borde posterior en el Node i).
La segunda parte será (inversión total de aristas o aristas posteriores totales del árbol R – recuento de aristas posteriores del Node i). Después de calcular este valor en cada Node, elegiremos el mínimo de ellos como nuestro resultado.
En el siguiente código, en la dirección del borde dada, se agrega el peso 0 y en la dirección inversa, se agrega el peso 1, que se usa para contar los bordes inversos en el método dfs.
Implementación:
C++
// C++ program to find min edge reversal to
// make every node reachable from root
#include <bits/stdc++.h>
using namespace std;
// method to dfs in tree and populates disRev values
int dfs(vector< pair<int, int> > g[],
pair<int, int> disRev[], bool visit[], int u)
{
// visit current node
visit[u] = true;
int totalRev = 0;
// looping over all neighbors
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].first;
if (!visit[v])
{
// distance of v will be one more than distance of u
disRev[v].first = disRev[u].first + 1;
// initialize back edge count same as
// parent node's count
disRev[v].second = disRev[u].second;
// if there is a reverse edge from u to i,
// then only update
if (g[u][i].second)
{
disRev[v].second = disRev[u].second + 1;
totalRev++;
}
totalRev += dfs(g, disRev, visit, v);
}
}
// return total reversal in subtree rooted at u
return totalRev;
}
// method prints root and minimum number of edge reversal
void printMinEdgeReverseForRootNode(int edges[][2], int e)
{
// number of nodes are one more than number of edges
int V = e + 1;
// data structure to store directed tree
vector< pair<int, int> > g[V];
// disRev stores two values - distance and back
// edge count from root node
pair<int, int> disRev[V];
bool visit[V];
int u, v;
for (int i = 0; i < e; i++)
{
u = edges[i][0];
v = edges[i][1];
// add 0 weight in direction of u to v
g[u].push_back(make_pair(v, 0));
// add 1 weight in reverse direction
g[v].push_back(make_pair(u, 1));
}
// initialize all variables
for (int i = 0; i < V; i++)
{
visit[i] = false;
disRev[i].first = disRev[i].second = 0;
}
int root = 0;
// dfs populates disRev data structure and
// store total reverse edge counts
int totalRev = dfs(g, disRev, visit, root);
// UnComment below lines to print each node's
// distance and edge reversal count from root node
/*
for (int i = 0; i < V; i++)
{
cout << i << " : " << disRev[i].first
<< " " << disRev[i].second << endl;
}
*/
int res = INT_MAX;
// loop over all nodes to choose minimum edge reversal
for (int i = 0; i < V; i++)
{
// (reversal in path to i) + (reversal
// in all other tree parts)
int edgesToRev = (totalRev - disRev[i].second) +
(disRev[i].first - disRev[i].second);
// choose minimum among all values
if (edgesToRev < res)
{
res = edgesToRev;
root = i;
}
}
// print the designated root and total
// edge reversal made
cout << root << " " << res << endl;
}
// Driver code to test above methods
int main()
{
int edges[][2] =
{
{0, 1},
{2, 1},
{3, 2},
{3, 4},
{5, 4},
{5, 6},
{7, 6}
};
int e = sizeof(edges) / sizeof(edges[0]);
printMinEdgeReverseForRootNode(edges, e);
return 0;
}
Java
// Java program to find min edge reversal to
// make every node reachable from root
import java.util.*;
class GFG
{
// pair class
static class pair
{
int first,second;
pair(int a ,int b)
{
first = a;
second = b;
}
}
// method to dfs in tree and populates disRev values
static int dfs(Vector<Vector< pair >> g,
pair disRev[], boolean visit[], int u)
{
// visit current node
visit[u] = true;
int totalRev = 0;
// looping over all neighbors
for (int i = 0; i < g.get(u).size(); i++)
{
int v = g.get(u).get(i).first;
if (!visit[v])
{
// distance of v will be one more than distance of u
disRev[v].first = disRev[u].first + 1;
// initialize back edge count same as
// parent node's count
disRev[v].second = disRev[u].second;
// if there is a reverse edge from u to i,
// then only update
if (g.get(u).get(i).second!=0)
{
disRev[v].second = disRev[u].second + 1;
totalRev++;
}
totalRev += dfs(g, disRev, visit, v);
}
}
// return total reversal in subtree rooted at u
return totalRev;
}
// method prints root and minimum number of edge reversal
static void printMinEdgeReverseForRootNode(int edges[][], int e)
{
// number of nodes are one more than number of edges
int V = e + 1;
// data structure to store directed tree
Vector<Vector< pair >> g=new Vector<Vector< pair >>();
for(int i = 0; i < V + 1; i++)
g.add(new Vector<pair>());
// disRev stores two values - distance and back
// edge count from root node
pair disRev[] = new pair[V];
for(int i = 0; i < V; i++)
disRev[i] = new pair(0, 0);
boolean visit[] = new boolean[V];
int u, v;
for (int i = 0; i < e; i++)
{
u = edges[i][0];
v = edges[i][1];
// add 0 weight in direction of u to v
g.get(u).add(new pair(v, 0));
// add 1 weight in reverse direction
g.get(v).add(new pair(u, 1));
}
// initialize all variables
for (int i = 0; i < V; i++)
{
visit[i] = false;
disRev[i].first = disRev[i].second = 0;
}
int root = 0;
// dfs populates disRev data structure and
// store total reverse edge counts
int totalRev = dfs(g, disRev, visit, root);
// UnComment below lines to print each node's
// distance and edge reversal count from root node
/*
for (int i = 0; i < V; i++)
{
cout << i << " : " << disRev[i].first
<< " " << disRev[i].second << endl;
}
*/
int res = Integer.MAX_VALUE;
// loop over all nodes to choose minimum edge reversal
for (int i = 0; i < V; i++)
{
// (reversal in path to i) + (reversal
// in all other tree parts)
int edgesToRev = (totalRev - disRev[i].second) +
(disRev[i].first - disRev[i].second);
// choose minimum among all values
if (edgesToRev < res)
{
res = edgesToRev;
root = i;
}
}
// print the designated root and total
// edge reversal made
System.out.println(root + " " + res );
}
// Driver code
public static void main(String args[])
{
int edges[][] =
{
{0, 1},
{2, 1},
{3, 2},
{3, 4},
{5, 4},
{5, 6},
{7, 6}
};
int e = edges.length;
printMinEdgeReverseForRootNode(edges, e);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find min edge reversal
# to make every node reachable from root
import sys
# Method to dfs in tree and populates
# disRev values
def dfs(g, disRev, visit, u):
# Visit current node
visit[u] = True
totalRev = 0
# Looping over all neighbors
for i in range(len(g[u])):
v = g[u][i][0]
if (not visit[v]):
# Distance of v will be one more
# than distance of u
disRev[v][0] = disRev[u][0] + 1
# Initialize back edge count same as
# parent node's count
disRev[v][1] = disRev[u][1]
# If there is a reverse edge from u to i,
# then only update
if (g[u][i][1]):
disRev[v][1] = disRev[u][1] + 1
totalRev += 1
totalRev += dfs(g, disRev, visit, v)
# Return total reversal in subtree rooted at u
return totalRev
# Method prints root and minimum number of
# edge reversal
def printMinEdgeReverseForRootNode(edges, e):
# Number of nodes are one more than
# number of edges
V = e + 1
# Data structure to store directed tree
g = [[] for i in range(V)]
# disRev stores two values - distance
# and back edge count from root node
disRev = [[0, 0] for i in range(V)]
visit = [False for i in range(V)]
# u, v
for i in range(e):
u = edges[i][0]
v = edges[i][1]
# Add 0 weight in direction of u to v
g[u].append([v, 0])
# Add 1 weight in reverse direction
g[v].append([u, 1])
# Initialize all variables
for i in range(V):
visit[i] = False
disRev[i][0] = disRev[i][1] = 0
root = 0
# dfs populates disRev data structure and
# store total reverse edge counts
totalRev = dfs(g, disRev, visit, root)
# UnComment below lines to preach node's
# distance and edge reversal count from root node
# for (i = 0 i < V i++)
# {
# cout << i << " : " << disRev[i][0]
# << " " << disRev[i][1] << endl
# }
res = sys.maxsize
# Loop over all nodes to choose
# minimum edge reversal
for i in range(V):
# (reversal in path to i) + (reversal
# in all other tree parts)
edgesToRev = ((totalRev - disRev[i][1]) +
(disRev[i][0] - disRev[i][1]))
# Choose minimum among all values
if (edgesToRev < res):
res = edgesToRev
root = i
# Print the designated root and total
# edge reversal made
print(root, res)
# Driver code
if __name__ == '__main__':
edges = [ [ 0, 1 ], [ 2, 1 ],
[ 3, 2 ], [ 3, 4 ],
[ 5, 4 ], [ 5, 6 ],
[ 7, 6 ] ]
e = len(edges)
printMinEdgeReverseForRootNode(edges, e)
# This code is contributed by mohit kumar 29
C#
// C# program to find min edge reversal to
// make every node reachable from root
using System;
using System.Collections.Generic;
class GFG
{
// pair class
public class pair
{
public int first,second;
public pair(int a, int b)
{
first = a;
second = b;
}
}
// method to dfs in tree and populates disRev values
static int dfs(List<List< pair >> g,
pair []disRev, Boolean []visit, int u)
{
// visit current node
visit[u] = true;
int totalRev = 0;
// looping over all neighbors
for (int i = 0; i < g[u].Count; i++)
{
int v = g[u][i].first;
if (!visit[v])
{
// distance of v will be one more
// than distance of u
disRev[v].first = disRev[u].first + 1;
// initialize back edge count same as
// parent node's count
disRev[v].second = disRev[u].second;
// if there is a reverse edge from u to i,
// then only update
if (g[u][i].second != 0)
{
disRev[v].second = disRev[u].second + 1;
totalRev++;
}
totalRev += dfs(g, disRev, visit, v);
}
}
// return total reversal in subtree rooted at u
return totalRev;
}
// method prints root and minimum number of edge reversal
static void printMinEdgeReverseForRootNode(int [,]edges, int e)
{
// number of nodes are one more than number of edges
int V = e + 1;
// data structure to store directed tree
List<List< pair >> g = new List<List< pair >>();
for(int i = 0; i < V + 1; i++)
g.Add(new List<pair>());
// disRev stores two values - distance and back
// edge count from root node
pair []disRev = new pair[V];
for(int i = 0; i < V; i++)
disRev[i] = new pair(0, 0);
Boolean []visit = new Boolean[V];
int u, v;
for (int i = 0; i < e; i++)
{
u = edges[i, 0];
v = edges[i, 1];
// add 0 weight in direction of u to v
g[u].Add(new pair(v, 0));
// add 1 weight in reverse direction
g[v].Add(new pair(u, 1));
}
// initialize all variables
for (int i = 0; i < V; i++)
{
visit[i] = false;
disRev[i].first = disRev[i].second = 0;
}
int root = 0;
// dfs populates disRev data structure and
// store total reverse edge counts
int totalRev = dfs(g, disRev, visit, root);
// UnComment below lines to print each node's
// distance and edge reversal count from root node
/*
for (int i = 0; i < V; i++)
{
cout << i << " : " << disRev[i].first
<< " " << disRev[i].second << endl;
}
*/
int res = int.MaxValue;
// loop over all nodes to choose minimum edge reversal
for (int i = 0; i < V; i++)
{
// (reversal in path to i) + (reversal
// in all other tree parts)
int edgesToRev = (totalRev - disRev[i].second) +
(disRev[i].first - disRev[i].second);
// choose minimum among all values
if (edgesToRev < res)
{
res = edgesToRev;
root = i;
}
}
// print the designated root and total
// edge reversal made
Console.WriteLine(root + " " + res);
}
// Driver code
public static void Main(String []args)
{
int [,]edges = {{0, 1}, {2, 1},
{3, 2}, {3, 4},
{5, 4}, {5, 6},
{7, 6}};
int e = edges.GetLength(0);
printMinEdgeReverseForRootNode(edges, e);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find min edge
// reversal to make every node reachable
// from root
class pair
{
constructor(a, b)
{
this.first = a;
this.second = b;
}
}
// Method to dfs in tree and populates
// disRev values
function dfs(g, disRev, visit, u)
{
// Visit current node
visit[u] = true;
let totalRev = 0;
// Looping over all neighbors
for(let i = 0; i < g[u].length; i++)
{
let v = g[u][i].first;
if (!visit[v])
{
// Distance of v will be one more
// than distance of u
disRev[v].first = disRev[u].first + 1;
// Initialize back edge count same as
// parent node's count
disRev[v].second = disRev[u].second;
// If there is a reverse edge from u to i,
// then only update
if (g[u][i].second != 0)
{
disRev[v].second = disRev[u].second + 1;
totalRev++;
}
totalRev += dfs(g, disRev, visit, v);
}
}
// Return total reversal in subtree
// rooted at u
return totalRev;
}
// Method prints root and minimum number
// of edge reversal
function printMinEdgeReverseForRootNode(edges, e)
{
// Number of nodes are one more
// than number of edges
let V = e + 1;
// Data structure to store directed tree
let g = [];
for(let i = 0; i < V + 1; i++)
g.push([]);
// disRev stores two values - distance and
// back edge count from root node
let disRev = new Array(V);
for(let i = 0; i < V; i++)
disRev[i] = new pair(0, 0);
let visit = new Array(V);
let u, v;
for(let i = 0; i < e; i++)
{
u = edges[i][0];
v = edges[i][1];
// Add 0 weight in direction of u to v
g[u].push(new pair(v, 0));
// Add 1 weight in reverse direction
g[v].push(new pair(u, 1));
}
// Initialize all variables
for(let i = 0; i < V; i++)
{
visit[i] = false;
disRev[i].first = disRev[i].second = 0;
}
let root = 0;
// dfs populates disRev data structure and
// store total reverse edge counts
let totalRev = dfs(g, disRev, visit, root);
// UnComment below lines to print each node's
// distance and edge reversal count from root node
/*
for (int i = 0; i < V; i++)
{
cout << i << " : " << disRev[i].first
<< " " << disRev[i].second << endl;
}
*/
let res = Number.MAX_VALUE;
// Loop over all nodes to choose
// minimum edge reversal
for(let i = 0; i < V; i++)
{
// (reversal in path to i) + (reversal
// in all other tree parts)
let edgesToRev = (totalRev - disRev[i].second) +
(disRev[i].first - disRev[i].second);
// Choose minimum among all values
if (edgesToRev < res)
{
res = edgesToRev;
root = i;
}
}
// Print the designated root and total
// edge reversal made
document.write(root + " " + res );
}
// Driver code
let edges = [ [ 0, 1 ], [ 2, 1 ],
[ 3, 2 ], [ 3, 4 ],
[ 5, 4 ], [ 5, 6 ],
[ 7, 6 ] ];
let e = edges.length;
printMinEdgeReverseForRootNode(edges, e);
// This code is contributed by rag2127
</script>
Producción
3 3
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA