Dado un número entero N y una array arr[] de M pares de tipo ( A i , B i ), la tarea es generar la permutación lexicográficamente más pequeña posible de 1 a N tal que cada A i ocurra antes que cada B i .
Ejemplos:
Entrada: N = 4, arr[] = { {2, 1}, {3, 4}, {2, 4} } Salida
: 2 1 3 4
Explicación: Las siguientes cinco permutaciones P satisfacen la condición:
(2, 1 , 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1).
El más pequeño lexicográficamente entre ellos es (2, 1, 3, 4).Entrada: N = 2, arr[] = { {2, 1} }
Salida: 2 1
Planteamiento: El problema se puede resolver usando el concepto de Grafo basado en la siguiente idea:
Considere un gráfico de N vértices donde hay un borde dirigido de A a B si A ocurre antes que B en la permutación.
- Entonces, el objetivo es encontrar una ordenación tal que cualquier vértice ocurra en la permutación después de que todos sus predecesores (los vértices que tienen aristas dirigidas a este) hayan ocurrido en la permutación.
- Mientras lo hace, muévase del valor mínimo al valor máximo posible para obtener la permutación lexicográficamente más pequeña.
Esto se puede hacer con la ayuda de la clasificación topológica .
- El ordenamiento topológico partirá de los vértices de grado 0 y en secuencia de menor a mayor valor.
- Una vez finalizada la clasificación topológica, si algún vértice aún no está incluido en la permutación, entonces no es posible dicha permutación.
Siga los pasos a continuación para resolver el problema:
- Inicialice un vector (digamos ans ) para almacenar la permutación resultante.
- Visite los M pares y cree bordes dirigidos desde el primer valor de arr[i] hasta el segundo valor de arr[i] . Además, aumente el grado de entrada del segundo valor de arr[i] en 1 .
- Ahora encuentre todos los elementos con grado 0 , empújelos en la permutación resultante en orden creciente y comience la ordenación topológica .
- Agregue cualquier vértice a la permutación cuando su grado de entrada sea 0 .
- Mantenga el orden lexicográfico mientras lo hace, es decir, muévase del valor más bajo al valor más alto.
- Tome la ayuda de min heap para realizar la clasificación topológica:
- Inicialmente mantenga los vértices con grado 0 en el montón.
- Luego extraiga el vértice de menor valor, agréguelo a ans , elimine todos sus bordes y disminuya el grado de entrada en 1 de todos los vértices conectados a él.
- Si el grado de entrada de cualquier vértice se convierte en 0 en este proceso, introdúzcalo en el montón.
- Devuelve ans como la permutación final requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to obtain the permutation
vector<int> Calculate(int n, int m,
vector<pair<int, int> > arr)
{
// Prepare an empty array ans
vector<int> ans;
vector<int> indegree(n);
vector<vector<int> > out(n);
// Build the directed graph
for (int i = 0; i < m; i++) {
int a = arr[i].first;
int b = arr[i].second;
a--;
b--;
// Calculate indegree of every element
indegree[b] = indegree[b] + 1;
// Store connection of each node
out[a].push_back(b);
}
// Declaring the min heap
priority_queue<int, vector<int>,
greater<int> >
heap;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) {
// Push elements in priority queue
// if indegree is 0
heap.push(i);
}
}
// Run topological sort
while (!heap.empty()) {
// Choose vertex with degree 0,
// denoted by i
int i = heap.top();
heap.pop();
// Push i+1 to the tail of ans
ans.push_back(i + 1);
// Remove i and edges going out from i
for (int j : out[i]) {
indegree[j] -= 1;
// In the process if any node's indegree
// becomes 0 then push the element
// to the priority queue
if (indegree[j] == 0) {
heap.push(j);
}
}
}
// If size of ans is not n then
// output would is not possible
if (ans.size() != n) {
ans.clear();
ans.push_back(-1);
}
return ans;
}
// Driver code
int main()
{
int N = 4, M = 3;
vector<pair<int, int> > arr
= { { 2, 1 }, { 3, 4 }, { 2, 4 } };
// Function call
vector<int> res = Calculate(N, M, arr);
for (int x : res)
cout << x << " ";
return 0;
}
Java
// Java program to implement above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to obtain the permutation
public static ArrayList<Integer> Calculate(int n, int m,
int arr[][])
{
// Prepare an empty array ans
ArrayList<Integer> ans = new ArrayList<Integer>();
int indegree[] = new int[n];
ArrayList<ArrayList<Integer> > out
= new ArrayList<ArrayList<Integer> >(n);
for (int i = 0; i < n; i++) {
out.add(new ArrayList<Integer>());
}
// Build the directed graph
for (int i = 0; i < m; i++) {
int a = arr[i][0];
int b = arr[i][1];
a--;
b--;
// Calculate indegree of every element
indegree[b] = indegree[b] + 1;
// Store connection of each node
out.get(a).add(b);
}
// Declaring the min heap
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) {
// Push elements in priority queue
// if indegree is 0
heap.add(i);
}
}
// Run topological sort
while (!heap.isEmpty()) {
// Choose vertex with degree 0,
// denoted by i
int i = heap.peek();
heap.poll();
// Push i+1 to the tail of ans
ans.add(i + 1);
// Remove i and edges going out from i
for (Integer j : out.get(i)) {
indegree[j] -= 1;
// In the process if any node's indegree
// becomes 0 then push the element
// to the priority queue
if (indegree[j] == 0) {
heap.add(j);
}
}
}
// If size of ans is not n then
// output would is not possible
if (ans.size() != n) {
ans.clear();
ans.add(-1);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 4, M = 3;
int arr[][] = { { 2, 1 }, { 3, 4 }, { 2, 4 } };
// Function call
ArrayList<Integer> res = Calculate(N, M, arr);
for (Integer x : res)
System.out.print(x + " ");
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python program to implement above approach def Calculate(n, m, arr): # Prepare an empty array ans ans = [] indegree = [0] * n out = [[] for i in range(n)] # Build the directed graph for i in range(m): a = arr[i][0] b = arr[i][1] a -= 1 b -= 1 # Calculate indegree of every element indegree[b] += 1 # Store connection of each node out[a].append(b) # Declaring the min heap heap = [] for i in range(n): if indegree[i] == 0: # Push elements in priority queue # if indegree is 0 heap.append(i) # Run topological sort while heap: # Choose vertex with degree 0, # denoted by i i = heap.pop(0) # Push i+1 to the tail of ans ans.append(i + 1) # Remove i and edges going out from i for j in out[i]: indegree[j] -= 1 # In the process if any node's indegree # becomes 0 then push the element # to the priority queue if indegree[j] == 0: heap.append(j) # If size of ans is not n then # output would is not possible if len(ans) != n: ans = [-1] return ans # Driver code if __name__ == '__main__': n = 4 m = 3 arr = [[2, 1], [3, 4], [2, 4]] res = Calculate(n, m, arr) print(res) # This code is contributed by abhinavprkash.
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG {
static List<int> Calculate(int n, int m, int[, ] arr)
{
// Prepare an empty array ans
List<int> ans = new List<int>();
int[] indegree = new int[n];
// for (int i = 0; i < n; i++)
// indegree[i] = 0;
List<List<int> > Out = new List<List<int> >();
for (var i = 0; i < n; i++)
Out.Add(new List<int>());
// Build the directed graph
for (var i = 0; i < m; i++) {
var a = arr[i, 0];
var b = arr[i, 1];
a -= 1;
b -= 1;
// Calculate indegree of every element
indegree[b] += 1;
// Store connection of each node
Out[a].Add(b);
}
// Declaring the min heap
List<int> heap = new List<int>();
for (var i = 0; i < n; i++) {
if (indegree[i] == 0) {
// Push elements in priority queue
// if indegree is 0
heap.Add(i);
}
}
// Run topological sort
while (heap.Count > 0) {
heap.Sort();
// Choose vertex with degree 0,
// denoted by i
var i = heap[0];
heap.RemoveAt(0);
// Push i+1 to the tail of ans
ans.Add(i + 1);
// Remove i and edges going out from i
for (var k = 0; k < Out[i].Count; k++) {
var j = Out[i][k];
indegree[j] -= 1;
// In the process if any node's indegree
// becomes 0 then push the element
// to the priority queue
if (indegree[j] == 0)
heap.Add(j);
}
}
// If size of ans is not n then
// output would is not possible
if (ans.Count != n) {
ans.Clear();
ans.Add(-1);
}
return ans;
}
// Driver code
public static void Main(string[] args)
{
var n = 4;
var m = 3;
int[, ] arr = { { 2, 1 }, { 3, 4 }, { 2, 4 } };
var res = Calculate(n, m, arr);
foreach(var i in res) Console.Write(i + " ");
}
}
// This code is contributed by phasing17
Javascript
//JavaScript program to implement above approach
function Calculate(n, m, arr)
{
// Prepare an empty array ans
var ans = [];
var indegree = new Array(n).fill(0);
var out = [];
for (var i = 0; i < n; i++)
out.push([ ]);
// Build the directed graph
for (var i = 0; i < m; i++)
{
var a = arr[i][0];
var b = arr[i][1];
a -= 1;
b -= 1;
// Calculate indegree of every element
indegree[b] += 1;
// Store connection of each node
out[a].push(b);
}
// Declaring the min heap
var heap = [];
for (var i = 0; i < n; i++)
{
if (indegree[i] == 0)
{
// Push elements in priority queue
// if indegree is 0
heap.push(i);
}
}
// Run topological sort
while (heap.length > 0)
{
// Choose vertex with degree 0,
// denoted by i
var i = heap.shift();
// Push i+1 to the tail of ans
ans.push(i + 1);
// Remove i and edges going out from i
for (var k = 0; k < out[i].length; k++)
{
var j = out[i][k];
indegree[j] -= 1;
// In the process if any node's indegree
// becomes 0 then push the element
// to the priority queue
if (indegree[j] == 0)
heap.push(j);
}
}
// If size of ans is not n then
// output would is not possible
if (ans.length != n)
ans = [-1];
return ans;
}
// Driver code
var n = 4;
var m = 3;
var arr = [[2, 1], [3, 4], [2, 4]];
var res = Calculate(n, m, arr);
console.log(res);
// This code is contributed by phasing17
Producción
2 1 3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tejasdhanait y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA