Dado un número entero N, la tarea es encontrar el número de permutaciones de números enteros del rango [1, N] que pueden formar un gráfico acíclico de acuerdo con las siguientes condiciones:
- Para cada 1 ≤ i ≤ N , encuentre el j más grande tal que 1 ≤ j < i y A[j] > A[i ], y agregue un borde no dirigido entre el Node i y el Node j .
- Para cada 1 ≤ i ≤ N , encuentre el j más pequeño tal que i < j ≤ N y A[j] > A[i] , y agregue un borde no dirigido entre el Node i y el Node j .
Ejemplos:
Entrada: 3
Salida: 4
Explicación:
{1, 2, 3}: Posible (Bordes del gráfico: { [1, 2], [2, 3] }. Por lo tanto, no existe ningún ciclo)
{1, 3, 2}: Posible (Bordes del gráfico: { [1, 3], [2, 3] }. Por lo tanto, no existe ningún ciclo)
{2, 1, 3}: No es posible (Bordes del gráfico: { [2, 3], [1, 3] , [1, 2] }. Por lo tanto, existe un ciclo)
{2, 3, 1}: Posible (Bordes del gráfico: { [2, 3], [1, 3] }. Por lo tanto, no existe un ciclo)
{3, 1 , 2}: No es posible (Bordes del gráfico: { [1, 2], [1, 3], [2, 3] }. Por lo tanto, el ciclo existe)
{3, 2, 1}: Posible (Bordes del gráfico: { [ 2, 3], [1, 2] }. Por lo tanto, no existe ningún ciclo)Entrada: 4
Salida: 8
Enfoque: siga los pasos a continuación para resolver el problema:
- Hay un total de N! arrays posibles que se pueden generar que consisten en permutaciones de enteros del rango [1, N] .
- De acuerdo con las condiciones dadas, si i, j, k (i < j < k) son índices del arreglo, entonces si A[i] > A[j] y A[j] < A[k] , entonces habrá ser un ciclo que consta de aristas { [A[j], A[i]], [A[j], A[k]], [A[i], A[k]]} .
- Al eliminar estas permutaciones, quedan 2 (N – 1) permutaciones posibles.
- Las permutaciones restantes dan solo dos posiciones posibles para enteros del rango [1, N – 1] y 1 posición posible para N .
Ilustración:
Para N = 3: la
permutación {2, 1, 3} contiene un ciclo como A[0] > A[1] y A[1] < A[2].
La permutación {3, 1, 2} contiene un ciclo como A[0] > A[1] y A[1] < A[2].
Todas las permutaciones restantes pueden generar un gráfico acíclico.
Por lo tanto, la cuenta de permutaciones válidas = 3! – 2 = 4 = 2 3 – 1
- Por lo tanto, escriba 2 N – 1 como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Find the count of possible graphs void possibleAcyclicGraph(int N) { cout << pow(2, N - 1); return; } // Driver Code int main() { int N = 4; possibleAcyclicGraph(N); return 0; }
Java
// Java implementation of // the above approach import java.util.*; class GFG{ // Find the count of // possible graphs static void possibleAcyclicGraph(int N) { System.out.print((int)Math.pow(2, N - 1)); return; } // Driver Code public static void main(String[] args) { int N = 4; possibleAcyclicGraph(N); } } // This code is contributed by Princi Singh
Python3
# Python3 implementation of above approach # Find the count of possible graphs def possibleAcyclicGraph(N): print(pow(2, N - 1)) return # Driver code if __name__ == '__main__': N = 4 possibleAcyclicGraph(N) # This code is contributed by mohit kumar 29
C#
// C# implementation of // the above approach using System; class GFG{ // Find the count of // possible graphs static void possibleAcyclicGraph(int N) { Console.Write((int)Math.Pow(2, N - 1)); return; } // Driver Code public static void Main() { int N = 4; possibleAcyclicGraph(N); } } // This code is contributed by sanjoy_62
Javascript
<script> // Javascript implementation of above approach // Find the count of // possible graphs function possibleAcyclicGraph(N) { document.write(Math.pow(2, N - 1)); return; } // Driver Code let N = 4; possibleAcyclicGraph(N); // This code is contributed by target_2 </script>
8
Complejidad de tiempo: O(logN)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por pradyumanagarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA