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: 1
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: 0
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