Número mínimo de bordes que se agregarán a un gráfico para satisfacer la condición dada

Dado un grafo que consta de N Nodes numerados de 0 a N – 1 y M aristas en forma de pares {a, b} , la tarea es encontrar el número mínimo de aristas que se agregarán al gráfico de manera que si existe un camino desde cualquier Node a hasta el Node b , entonces debería haber caminos desde el Node a hasta los Nodes [ a + 1, a + 2, a + 3, …, b – 1] también.

Ejemplos:  

Entrada: N = 7, M = 3, Edges[][] = {{1, 5}, {2, 4}, {3, 4}} 
Salida:
Explicación: 
Hay una ruta de 1 a 5. Entonces debe haber rutas de 1 a 2, 3 y 4 también. 
Sumar una arista {1, 2} será suficiente para llegar a los otros dos Nodes del gráfico.

Entrada: N = 8, M = 3 Bordes[][] = {{1, 2}, {2, 3}, {3, 4}} 
Salida:
 

Enfoque:
La idea es usar un conjunto disjunto o una unión . Cada componente del conjunto disjunto debe tener Nodes consecutivos. Esto se puede hacer manteniendo arrays de Node_máximo[ ] y Node_mínimo[] para almacenar el valor máximo y mínimo de los Nodes en cada componente respectivamente. Siga los pasos a continuación para resolver el problema:

  • Crea una estructura para la unión de conjuntos disjuntos.
  • Inicialice la respuesta como 0 e itere sobre todos los Nodes en el gráfico para obtener el componente del Node actual.
  • Si el componente no se visita , márquelo como visitado.
  • Ahora, itere desde el valor mínimo hasta el valor máximo de ese componente y verifique si los Nodes están en el mismo componente con el Node actual o no, combínelos en un componente e incremente la respuesta en 1 .
  • Finalmente, imprime la respuesta .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#define MOD 1000000007
 
#define int long long int
using namespace std;
 
// Disjoint Set Union
struct dsu {
 
    // Stores the parent
    // of each node
    vector<int> parent;
 
    // Storing maximum value
    // in each component
    vector<int> maximum_node;
 
    // Stores the minimum value
    // in each component
    vector<int> minimum_node;
 
    // Stores the visited nodes
    vector<int> visited;
 
    // Function to initialize the
    // values in vectors
    void init(int n)
    {
        // Initialize the size of
        // vectors as n
        parent.resize(n);
        maximum_node.resize(n);
        minimum_node.resize(n);
        visited.resize(n);
 
        for (int i = 0; i < n; i++) {
 
            // Initially every component
            // has only one node
            parent[i] = i;
            maximum_node[i] = i;
            minimum_node[i] = i;
 
            // Mark unvisited
            visited[i] = 0;
        }
    }
 
    // Function to get identifier node
    // (superparent) for each component
    int getsuperparent(int x)
    {
 
        // If parent of a node is that
        // node itself then the node is
        // superparent of that component
        return x == parent[x]
                   ? x
                   : parent[x]
                     = getsuperparent(parent[x]);
    }
 
    // Function to perform union of two
    // different components
    void unite(int x, int y)
    {
 
        int superparent_x = getsuperparent(x);
        int superparent_y = getsuperparent(y);
 
        // Set superparent of y as the
        // parent of superparent of x
        parent[superparent_x] = superparent_y;
 
        // Update the maximum node
        // in the component containing y
        maximum_node[superparent_y]
            = max(maximum_node[superparent_y],
                  maximum_node[superparent_x]);
 
        // Update the minimum node
        // in the component containing y
        minimum_node[superparent_y]
            = min(minimum_node[superparent_y],
                  minimum_node[superparent_x]);
    }
} G;
 
// Function to find the minimum number
// of edges to be added to the Graph
int minimumEdgesToBeAdded(int n)
{
    // Stores the answer
    int answer = 0;
 
    // Iterate over all nodes
    for (int i = 0; i < n; i++) {
 
        // Get the superparent of
        // the current node
        int temp = G.getsuperparent(i);
 
        // If the node is not visited
        if (!G.visited[temp]) {
 
            // Set the node as visited
            G.visited[temp] = 1;
 
            // Iterate from the minimum
            // value to maximum value in
            // the current component
            for (int j = G.minimum_node[temp];
                 j <= G.maximum_node[temp]; j++) {
 
                // If the nodes are in
                // different components
                if (G.getsuperparent(j)
                    != G.getsuperparent(i)) {
 
                    // Unite them
                    G.unite(i, j);
 
                    // Increment the answer
                    answer++;
                }
            }
        }
    }
 
    // Return the answer
    return answer;
}
 
// Driver Code
int32_t main()
{
    int N = 7, M = 3;
 
    G.init(N);
 
    // Insert edges
    G.unite(1, 5);
    G.unite(2, 4);
    G.unite(3, 4);
 
    cout << minimumEdgesToBeAdded(N);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
static final int MOD = 1000000007;
 
// Disjoint Set Union
static class dsu
{
    public dsu(){}
 
    // Stores the parent
    // of each node
    int[] parent;
 
    // Storing maximum value
    // in each component
    int[] maximum_node;
 
    // Stores the minimum value
    // in each component
    int[] minimum_node;
 
    // Stores the visited nodes
    int[] visited;
 
    // Function to initialize the
    // values in vectors
    void init(int n)
    {
         
        // Initialize the size of
        // vectors as n
        parent = new int[n];
        maximum_node = new int[n];
        minimum_node = new int[n];
        visited = new int[n];
 
        for(int i = 0; i < n; i++)
        {
             
            // Initially every component
            // has only one node
            parent[i] = i;
            maximum_node[i] = i;
            minimum_node[i] = i;
 
            // Mark unvisited
            visited[i] = 0;
        }
    }
 
    // Function to get identifier node
    // (superparent) for each component
    int getsuperparent(int x)
    {
 
        // If parent of a node is that
        // node itself then the node is
        // superparent of that component
        if(x == parent[x])
            return x;
        else
        {
            parent[x] = getsuperparent(parent[x]);
            return parent[x];
        }
    }
 
    // Function to perform union of two
    // different components
    void unite(int x, int y)
    {
        int superparent_x = getsuperparent(x);
        int superparent_y = getsuperparent(y);
 
        // Set superparent of y as the
        // parent of superparent of x
        parent[superparent_x] = superparent_y;
 
        // Update the maximum node
        // in the component containing y
        maximum_node[superparent_y] = Math.max(
        maximum_node[superparent_y],
        maximum_node[superparent_x]);
 
        // Update the minimum node
        // in the component containing y
        minimum_node[superparent_y] = Math.min(
        minimum_node[superparent_y],
        minimum_node[superparent_x]);
    }
};
 
static dsu G = new dsu();
 
// Function to find the minimum number
// of edges to be added to the Graph
static int minimumEdgesToBeAdded(int n)
{
     
    // Stores the answer
    int answer = 0;
 
    // Iterate over all nodes
    for(int i = 0; i < n; i++)
    {
         
        // Get the superparent of
        // the current node
        int temp = G.getsuperparent(i);
 
        // If the node is not visited
        if (G.visited[temp] == 0)
        {
             
            // Set the node as visited
            G.visited[temp] = 1;
 
            // Iterate from the minimum
            // value to maximum value in
            // the current component
            for(int j = G.minimum_node[temp];
                   j <= G.maximum_node[temp]; j++)
            {
                 
                // If the nodes are in
                // different components
                if (G.getsuperparent(j) !=
                    G.getsuperparent(i))
                {
                     
                    // Unite them
                    G.unite(i, j);
 
                    // Increment the answer
                    answer++;
                }
            }
        }
    }
     
    // Return the answer
    return answer;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7;
 
    G.init(N);
 
    // Insert edges
    G.unite(1, 5);
    G.unite(2, 4);
    G.unite(3, 4);
 
    System.out.print(minimumEdgesToBeAdded(N));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
MOD = 1000000007
 
# Disjoint Set Union
class dsu:
 
    # Function to initialize the
    # values in vectors
    def __init__(self, n: int) -> None:
         
        # Stores the parent
        # of each node
        self.parent = [i for i in range(n)]
         
        # Storing maximum value
        # in each component
        self.maximum_node = [i for i in range(n)]
         
        # Stores the minimum value
        # in each component
        self.minimum_node = [i for i in range(n)]
         
        # Stores the visited nodes
        self.visited = [0] * n
 
    # Function to get identifier node
    # (superparent) for each component
    def getsuperparent(self, x: int) -> int:
         
        # If parent of a node is that
        # node itself then the node is
        # superparent of that component
        if x == self.parent[x]:
            return x
        else:
            self.parent[x] = self.getsuperparent(
                self.parent[x])
            return self.parent[x]
 
    # Function to perform union of two
    # different components
    def unite(self, x: int, y: int) -> None:
 
        superparent_x = self.getsuperparent(x)
        superparent_y = self.getsuperparent(y)
 
        # Set superparent of y as the
        # parent of superparent of x
        self.parent[superparent_x] = superparent_y
 
        # Update the maximum node
        # in the component containing y
        self.maximum_node[superparent_y] = max(
            self.maximum_node[superparent_y],
            self.maximum_node[superparent_x])
 
        # Update the minimum node
        # in the component containing y
        self.minimum_node[superparent_y] = min(
            self.minimum_node[superparent_y],
            self.minimum_node[superparent_x])
 
# Function to find the minimum number
# of edges to be added to the Graph
def minimumEdgesToBeAdded(n: int) -> int:
 
    global G
 
    # Stores the answer
    answer = 0
 
    # Iterate over all nodes
    for i in range(n):
 
        # Get the superparent of
        # the current node
        temp = G.getsuperparent(i)
 
        # If the node is not visited
        if (not G.visited[temp]):
 
            # Set the node as visited
            G.visited[temp] = 1
 
            # Iterate from the minimum
            # value to maximum value in
            # the current component
            for j in range(G.minimum_node[temp],
                           G.maximum_node[temp] + 1):
                                
                # If the nodes are in
                # different components
                if (G.getsuperparent(j) !=
                    G.getsuperparent(i)):
 
                    # Unite them
                    G.unite(i, j)
 
                    # Increment the answer
                    answer += 1
 
    # Return the answer
    return answer
 
# Driver Code
if __name__ == "__main__":
 
    N = 7
    M = 3
 
    G = dsu(N)
 
    # Insert edges
    G.unite(1, 5)
    G.unite(2, 4)
    G.unite(3, 4)
     
    print(minimumEdgesToBeAdded(N))
 
# This code is contributed by sanjeev2552

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
//static readonly int MOD = 1000000007;
 
// Disjoint Set Union
class dsu
{
    public dsu(){}
 
    // Stores the parent
    // of each node
    public int[] parent;
 
    // Storing maximum value
    // in each component
    public int[] maximum_node;
 
    // Stores the minimum value
    // in each component
    public int[] minimum_node;
 
    // Stores the visited nodes
    public int[] visited;
 
    // Function to initialize the
    // values in vectors
    public void init(int n)
    {
         
        // Initialize the size of
        // vectors as n
        parent = new int[n];
        maximum_node = new int[n];
        minimum_node = new int[n];
        visited = new int[n];
 
        for(int i = 0; i < n; i++)
        {
             
            // Initially every component
            // has only one node
            parent[i] = i;
            maximum_node[i] = i;
            minimum_node[i] = i;
 
            // Mark unvisited
            visited[i] = 0;
        }
    }
 
    // Function to get identifier node
    // (superparent) for each component
    public int getsuperparent(int x)
    {
 
        // If parent of a node is that
        // node itself then the node is
        // superparent of that component
        if(x == parent[x])
            return x;
        else
        {
            parent[x] = getsuperparent(parent[x]);
            return parent[x];
        }
    }
 
    // Function to perform union of two
    // different components
    public void unite(int x, int y)
    {
        int superparent_x = getsuperparent(x);
        int superparent_y = getsuperparent(y);
 
        // Set superparent of y as the
        // parent of superparent of x
        parent[superparent_x] = superparent_y;
 
        // Update the maximum node
        // in the component containing y
        maximum_node[superparent_y] = Math.Max(
        maximum_node[superparent_y],
        maximum_node[superparent_x]);
 
        // Update the minimum node
        // in the component containing y
        minimum_node[superparent_y] = Math.Min(
        minimum_node[superparent_y],
        minimum_node[superparent_x]);
    }
};
 
static dsu G = new dsu();
 
// Function to find the minimum number
// of edges to be added to the Graph
static int minimumEdgesToBeAdded(int n)
{
     
    // Stores the answer
    int answer = 0;
 
    // Iterate over all nodes
    for(int i = 0; i < n; i++)
    {
         
        // Get the superparent of
        // the current node
        int temp = G.getsuperparent(i);
 
        // If the node is not visited
        if (G.visited[temp] == 0)
        {
             
            // Set the node as visited
            G.visited[temp] = 1;
 
            // Iterate from the minimum
            // value to maximum value in
            // the current component
            for(int j = G.minimum_node[temp];
                   j <= G.maximum_node[temp]; j++)
            {
                 
                // If the nodes are in
                // different components
                if (G.getsuperparent(j) !=
                    G.getsuperparent(i))
                {
                     
                    // Unite them
                    G.unite(i, j);
 
                    // Increment the answer
                    answer++;
                }
            }
        }
    }
     
    // Return the answer
    return answer;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 7;
 
    G.init(N);
 
    // Insert edges
    G.unite(1, 5);
    G.unite(2, 4);
    G.unite(3, 4);
 
    Console.Write(minimumEdgesToBeAdded(N));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
var MOD = 1000000007;
 
// Stores the parent
// of each node
var parent = [];
// Storing maximum value
// in each component
var maximum_node = [];
// Stores the minimum value
// in each component
var minimum_node = [];
// Stores the visited nodes
var visited = [];
// Function to initialize the
// values in vectors
function init(n)
{
     
    // Initialize the size of
    // vectors as n
    parent = Array(n);
    maximum_node = Array(n);
    minimum_node = Array(n);
    visited = Array(n);
    for(var i = 0; i < n; i++)
    {
         
        // Initially every component
        // has only one node
        parent[i] = i;
        maximum_node[i] = i;
        minimum_node[i] = i;
        // Mark unvisited
        visited[i] = 0;
    }
}
// Function to get identifier node
// (superparent) for each component
function getsuperparent(x)
{
    // If parent of a node is that
    // node itself then the node is
    // superparent of that component
    if(x == parent[x])
        return x;
    else
    {
        parent[x] = getsuperparent(parent[x]);
        return parent[x];
    }
}
// Function to perform union of two
// different components
function unite(x, y)
{
    var superparent_x = getsuperparent(x);
    var superparent_y = getsuperparent(y);
    // Set superparent of y as the
    // parent of superparent of x
    parent[superparent_x] = superparent_y;
    // Update the maximum node
    // in the component containing y
    maximum_node[superparent_y] = Math.max(
        maximum_node[superparent_y],
        maximum_node[superparent_x]);
    // Update the minimum node
    // in the component containing y
    minimum_node[superparent_y] = Math.min(
        minimum_node[superparent_y],
        minimum_node[superparent_x]);
}
 
// Function to find the minimum number
// of edges to be added to the Graph
function minimumEdgesToBeAdded(n)
{
     
    // Stores the answer
    var answer = 0;
 
    // Iterate over all nodes
    for(var i = 0; i < n; i++)
    {
         
        // Get the superparent of
        // the current node
        var temp = getsuperparent(i);
 
        // If the node is not visited
        if (visited[temp] == 0)
        {
             
            // Set the node as visited
            visited[temp] = 1;
 
            // Iterate from the minimum
            // value to maximum value in
            // the current component
            for(var j = minimum_node[temp];
                   j <= maximum_node[temp]; j++)
            {
                 
                // If the nodes are in
                // different components
                if (getsuperparent(j) !=
                    getsuperparent(i))
                {
                     
                    // Unite them
                    unite(i, j);
 
                    // Increment the answer
                    answer++;
                }
            }
        }
    }
     
    // Return the answer
    return answer;
}
 
// Driver Code
var N = 7;
init(N);
// Insert edges
unite(1, 5);
unite(2, 4);
unite(3, 4);
document.write(minimumEdgesToBeAdded(N));
 
 
</script>
Producción: 

1

 

Complejidad temporal: O(N), donde N es el número de Nodes del gráfico.
Espacio Auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por mohitkumarbt2k18 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 *