Encuentre la permutación de valor máximo de un gráfico

Dado un gráfico que contiene N Nodes. Para cualquier permutación de Nodes P ₁ , P ₂ , P ₃ , …, P _N el valor de la permutación se define como el número de índices que tienen al menos 1 Node a la izquierda que tiene una arista. Encuentre el valor máximo en todas las permutaciones.
Ejemplos: 
 

Entrada: N = 3, bordes[] = {{1, 2}, {2, 3}} 
Salida: 2 
Considere la permutación 2 1 3 El 
Node 1 tiene el Node 2 a la izquierda y hay un borde que los conecta en la gráfica. 
El Node 3 tiene el Node 2 a la izquierda y hay un borde que los conecta en el gráfico.
Entrada: N = 4, bordes[] = {{1, 3}, {2, 4}} 
Salida: 2 
Considere la permutación 1 2 3 4 El 
Node 3 tiene el Node 1 a la izquierda y hay un borde que los conecta en el gráfico. 
El Node 4 tiene el Node 2 a la izquierda y hay un borde que los conecta en el gráfico. 
 

Enfoque: Comencemos con cualquier Node al principio, podemos continuar con cualquier Node adyacente y repetir el proceso. Esto se parece a un recorrido dfs en el que cada Node, excepto el primero, tiene un Node anterior con el que comparte un borde. Entonces, para cada componente conectado, el valor máximo que podemos obtener para la permutación de los Nodes de este componente es Tamaño del componente – 1 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of nodes
// in the current connected component
int dfs(int x, vector<int> adj[], int vis[])
{
    // Initialise size to 1
    int sz = 1;
 
    // Mark the node as visited
    vis[x] = 1;
 
    // Start a dfs for every unvisited
    // adjacent node
    for (auto ch : adj[x])
        if (!vis[ch])
            sz += dfs(ch, adj, vis);
 
    // Return the number of nodes in
    // the current connected component
    return sz;
}
 
// Function to return the maximum value
// of the required permutation
int maxValue(int n, vector<int> adj[])
{
    int val = 0;
    int vis[n + 1] = { 0 };
 
    // For each connected component
    // add the corresponding value
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            val += dfs(i, adj, vis) - 1;
    return val;
}
 
// Driver code
int main()
{
    int n = 3;
    vector<int> adj[n + 1] = { { 1, 2 }, { 2, 3 } };
    cout << maxValue(n, adj);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
static int vis[];
 
// Function to return the number of nodes
// in the current connected component
static int dfs(int x, Vector<Vector<Integer>> adj)
{
    // Initialise size to 1
    int sz = 1;
 
    // Mark the node as visited
    vis[x] = 1;
 
    // Start a dfs for every unvisited
    // adjacent node
    for (int i = 0; i < adj.get(x).size(); i++)
        if (vis[adj.get(x).get(i)] == 0)
            sz += dfs(adj.get(x).get(i), adj);
 
    // Return the number of nodes in
    // the current connected component
    return sz;
}
 
// Function to return the maximum value
// of the required permutation
static int maxValue(int n, Vector<Vector<Integer>> adj)
{
    int val = 0;
    vis = new int[n + 1];
     
    for (int i = 0; i < n; i++)
    vis[i] = 0;
 
    // For each connected component
    // add the corresponding value
    for (int i = 0; i < n; i++)
        if (vis[i] == 0)
            val += dfs(i, adj) - 1;
    return val;
}
 
// Driver code
public static void main(String args[])
{
    int n = 3;
    Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>() ;
     
    // create the graph
    Vector<Integer> v = new Vector<Integer>();
    v.add(0);
    v.add(1);
    Vector<Integer> v1 = new Vector<Integer>();
    v1.add(1);
    v1.add(2);
     
    adj.add(v);
    adj.add(v1);
    adj.add(new Vector<Integer>());
     
    System.out.println( maxValue(n, adj));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Function to return the number of nodes
# in the current connected component
def dfs(x, adj, vis):
 
    # Initialise size to 1
    sz = 1
 
    # Mark the node as visited
    vis[x] = 1
 
    # Start a dfs for every unvisited
    # adjacent node
    for ch in adj:
        if (not vis[ch]):
            sz += dfs(ch, adj, vis)
 
    # Return the number of nodes in
    # the current connected component
    return sz
 
# Function to return the maximum value
# of the required permutation
def maxValue(n, adj):
 
    val = 0
    vis = [0] * (n + 1)
 
    # For each connected component
    # add the corresponding value
    for i in range(1, n + 1):
        if (not vis[i]):
            val += dfs(i, adj, vis) - 1
    return val
 
# Driver Code
if __name__ == '__main__':
    n = 3
    adj = [1, 2 , 2, 3]
    print(maxValue(n, adj))
 
# This code is contributed by
# SHUBHAMSINGH10

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int []vis ;
 
// Function to return the number of nodes
// in the current connected component
static int dfs(int x, List<List<int>> adj)
{
    // Initialise size to 1
    int sz = 1;
 
    // Mark the node as visited
    vis[x] = 1;
 
    // Start a dfs for every unvisited
    // adjacent node
    for (int i = 0; i < adj[x].Count; i++)
        if (vis[adj[x][i]] == 0)
            sz += dfs(adj[x][i], adj);
 
    // Return the number of nodes in
    // the current connected component
    return sz;
}
 
// Function to return the maximum value
// of the required permutation
static int maxValue(int n, List<List<int>> adj)
{
    int val = 0;
    vis = new int[n + 1];
     
    for (int i = 0; i < n; i++)
        vis[i] = 0;
 
    // For each connected component
    // add the corresponding value
    for (int i = 0; i < n; i++)
        if (vis[i] == 0)
            val += dfs(i, adj) - 1;
    return val;
}
 
// Driver code
public static void Main(String []args)
{
    int n = 3;
    List<List<int>> adj = new List<List<int>>() ;
     
    // create the graph
    List<int> v = new List<int>();
    v.Add(0);
    v.Add(1);
    List<int> v1 = new List<int>();
    v1.Add(1);
    v1.Add(2);
     
    adj.Add(v);
    adj.Add(v1);
    adj.Add(new List<int>());
     
    Console.WriteLine( maxValue(n, adj));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
// Function to return the number of nodes
// in the current connected component
function dfs(x, adj, vis)
{
    if(x>1)
        return 1;
         
    // Initialise size to 1
    var sz = 1;
 
    // Mark the node as visited
    vis[x] = 1;
    // Start a dfs for every unvisited
    // adjacent node
    adj[x].forEach(ch => {
         
        if (!vis[ch])
            sz += dfs(ch, adj, vis);
    });
 
    // Return the number of nodes in
    // the current connected component
    return sz;
}
 
// Function to return the maximum value
// of the required permutation
function maxValue(n, adj)
{
    var val = 0;
    var vis = Array(n+1).fill(0);
 
    // For each connected component
    // add the corresponding value
    for (var i = 0; i < n; i++)
        if (!vis[i])
            val += dfs(i, adj, vis) - 1;
    return val;
}
 
// Driver code
var n = 2;
var adj =  [ [ 0, 1 ], [ 1, 2] ];
document.write( maxValue(n, adj));
 
// This code is contributed by famously.
</script>

2

Complejidad de tiempo: O(N)