Convertir gráfico dirigido en un árbol

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *