Dada una array arr[] de tamaño N . Hay una arista de i a arr[i] . La tarea es convertir este gráfico dirigido en un árbol cambiando algunos de los bordes. Si para algún i , arr[i] = i entonces i representa la raíz del árbol. En caso de múltiples respuestas imprima cualquiera de ellas.
Ejemplos:
Entrada: arr[] = {6, 6, 0, 1, 4, 3, 3, 4, 0}
Salida: {6, 6, 0, 1, 4, 3, 4, 4, 0}
Entrada: arr[] = {1, 2, 0};
Salida: {0, 2, 0}.
Enfoque: Considere la segunda imagen de ejemplo anterior que muestra un ejemplo de un gráfico funcional. Consiste en dos ciclos 1, 6, 3 y 4. Nuestro objetivo es hacer que el gráfico consista en exactamente un ciclo de exactamente un vértice enlazado a sí mismo.
La operación de cambio equivale a quitar alguna arista saliente y añadir una nueva, yendo a otro vértice. En primer lugar, hagamos que nuestro gráfico contenga solo un ciclo. Para ello, se puede elegir cualquiera de los ciclos inicialmente presentados y decir que será el único. Luego, uno debe considerar cada otro ciclo, eliminar cualquiera de sus bordes dentro del ciclo y reemplazarlo con un borde que vaya a cualquiera de los vértices del ciclo elegido. Así el ciclo se romperá y sus vértices (junto con los del árbol) se conectarán al único ciclo elegido. Uno tendrá que hacer exactamenteCycleCount – 1 tales operaciones. Tenga en cuenta que la eliminación de cualquier borde que no sea de ciclo no tiene sentido, porque no rompe ningún ciclo.
Lo siguiente es hacer que la longitud del ciclo sea igual a 1. Eso ya podría estar satisfecho, si uno elige un ciclo de longitud mínima y esta longitud es igual a 1. Así, si el gráfico inicial contiene cualquier ciclo de longitud 1, estamos Hecho con CycleCount – 1 operaciones. De lo contrario, el ciclo contiene más de un vértice. Se puede arreglar con exactamente una operación: uno solo necesita romper cualquiera de los bordes del ciclo, digamos desde u hasta arr[u], y agregar un borde desde u hasta u. El grafo seguirá consistiendo en un ciclo, pero constará de un vértice en bucle propio. En ese caso, hemos terminado con las operaciones de CycleCount.
Para realizar todas las operaciones anteriores, se puede utilizar la estructura DSU o simplemente una serie de DFS. Tenga en cuenta que no es necesario realizar la eliminación y creación de bordes, solo se necesita analizar el gráfico inicial.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to convert directed graph into tree #include <bits/stdc++.h> using namespace std; // Function to find root of the vertex int find(int x, int a[], int vis[], int root[]) { if (vis[x]) return root[x]; vis[x] = 1; root[x] = x; root[x] = find(a[x], a, vis, root); return root[x]; } // Function to convert directed graph into tree void Graph_to_tree(int a[], int n) { // Vis array to check if an index is visited or not // root[] array is to store parent of each vertex int vis[n] = { 0 }, root[n] = { 0 }; // Find parent of each parent for (int i = 0; i < n; i++) find(a[i], a, vis, root); // par stores the root of the resulting tree int par = -1; for (int i = 0; i < n; i++) if (i == a[i]) par = i; // If no self loop exists if (par == -1) { for (int i = 0; i < n; i++) { // Make vertex in a cycle as root of the tree if (i == find(a[i], a, vis, root)) { par = i; a[i] = i; break; } } } // Remove all cycles for (int i = 0; i < n; i++) { if (i == find(a[i], a, vis, root)) { a[i] = par; } } // Print the resulting array for (int i = 0; i < n; i++) cout << a[i] << " "; } // Driver code to test above functions int main() { int a[] = { 6, 6, 0, 1, 4, 3, 3, 4, 0 }; int n = sizeof(a) / sizeof(a[0]); // Function call Graph_to_tree(a, n); }
Java
// Java program to convert // directed graph into tree import java.util.*; class GFG { // Function to find root of the vertex static int find(int x, int a[], int vis[], int root[]) { if (vis[x] == 1) return root[x]; vis[x] = 1; root[x] = x; root[x] = find(a[x], a, vis, root); return root[x]; } // Function to convert directed graph into tree static void Graph_to_tree(int a[], int n) { // Vis array to check if an index is // visited or not root[] array is to // store parent of each vertex int []vis = new int[n]; int []root = new int[n]; // Find parent of each parent for (int i = 0; i < n; i++) find(a[i], a, vis, root); // par stores the root of the resulting tree int par = -1; for (int i = 0; i < n; i++) if (i == a[i]) par = i; // If no self loop exists if (par == -1) { for (int i = 0; i < n; i++) { // Make vertex in a cycle as root of the tree if (i == find(a[i], a, vis, root)) { par = i; a[i] = i; break; } } } // Remove all cycles for (int i = 0; i < n; i++) { if (i == find(a[i], a, vis, root)) { a[i] = par; } } // Print the resulting array for (int i = 0; i < n; i++) System.out.print(a[i] + " "); } // Driver Code static public void main ( String []arr) { int a[] = { 6, 6, 0, 1, 4, 3, 3, 4, 0 }; int n = a.length; // Function call Graph_to_tree(a, n); } } // This code is contributed by 29AjayKumar
Python3
# A Python3 program to convert # directed graph into tree # Function to find root of the vertex def find(x, a, vis, root): if vis[x]: return root[x] vis[x] = 1 root[x] = x root[x] = find(a[x], a, vis, root) return root[x] # Function to convert directed graph into tree def Graph_To_Tree(a, n): # Vis array to check if an index is visited or not # root[] array is to store parent of each vertex vis = [0] * n root = [0] * n # Find parent of each parent for i in range(n): find(a[i], a, vis, root) # par stores the root of the resulting tree par = -1 for i in range(n): if i == a[i]: par = i # If no self loop exists if par == -1: for i in range(n): # Make vertex in a cycle as root of the tree if i == find(a[i], a, vis, root): par = i a[i] = i break # Remove all cycles for i in range(n): if i == find(a[i], a, vis, root): a[i] = par # Print the resulting array for i in range(n): print(a[i], end = " ") # Driver Code if __name__ == "__main__": a = [6, 6, 0, 1, 4, 3, 3, 4, 0] n = len(a) # Function call Graph_To_Tree(a, n) # This code is contributed by # sanjeev2552
C#
// C# program to convert // directed graph into tree using System; using System.Collections.Generic; class GFG { // Function to find root of the vertex static int find(int x, int []a, int []vis, int []root) { if (vis[x] == 1) return root[x]; vis[x] = 1; root[x] = x; root[x] = find(a[x], a, vis, root); return root[x]; } // Function to convert directed graph into tree static void Graph_to_tree(int []a, int n) { // Vis array to check if an index is // visited or not root[] array is to // store parent of each vertex int []vis = new int[n]; int []root = new int[n]; // Find parent of each parent for (int i = 0; i < n; i++) find(a[i], a, vis, root); // par stores the root of the resulting tree int par = -1; for (int i = 0; i < n; i++) if (i == a[i]) par = i; // If no self loop exists if (par == -1) { for (int i = 0; i < n; i++) { // Make vertex in a cycle as root of the tree if (i == find(a[i], a, vis, root)) { par = i; a[i] = i; break; } } } // Remove all cycles for (int i = 0; i < n; i++) { if (i == find(a[i], a, vis, root)) { a[i] = par; } } // Print the resulting array for (int i = 0; i < n; i++) Console.Write(a[i] + " "); } // Driver Code static public void Main ( String []arr) { int []a = { 6, 6, 0, 1, 4, 3, 3, 4, 0 }; int n = a.Length; // Function call Graph_to_tree(a, n); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript program to convert // directed graph into tree // Function to find root of the vertex function find(x, a, vis, root) { if (vis[x] == 1) return root[x]; vis[x] = 1; root[x] = x; root[x] = find(a[x], a, vis, root); return root[x]; } // Function to convert directed graph into tree function Graph_to_tree(a, n) { // Vis array to check if an index is // visited or not root[] array is to // store parent of each vertex var vis = Array(n).fill(0); var root = Array(n).fill(0); // Find parent of each parent for (var i = 0; i < n; i++) find(a[i], a, vis, root); // par stores the root of the resulting tree var par = -1; for (var i = 0; i < n; i++) if (i == a[i]) par = i; // If no self loop exists if (par == -1) { for (var i = 0; i < n; i++) { // Make vertex in a cycle as root of the tree if (i == find(a[i], a, vis, root)) { par = i; a[i] = i; break; } } } // Remove all cycles for (var i = 0; i < n; i++) { if (i == find(a[i], a, vis, root)) { a[i] = par; } } // Print the resulting array for (var i = 0; i < n; i++) document.write(a[i] + " "); } // Driver Code var a = [6, 6, 0, 1, 4, 3, 3, 4, 0]; var n = a.length; // Function call Graph_to_tree(a, n); // This code is contributed by rrrtnx. </script>
6 6 0 1 4 3 4 4 0
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA