K-ésimo Node más grande entre todos los Nodes conectados directamente al Node dado en un gráfico no dirigido

Dadas dos arrays u y v , que representan un gráfico tal que hay un borde no dirigido de u[i] a v[i] (0 ≤ v[i], u[i] < N) y cada Node tiene algún valor val[ yo] (0 ≤ yo < N). Para cada Node, si los Nodes conectados directamente a él están ordenados en orden descendente según sus valores (en caso de valores iguales, ordénelo según sus índices en orden ascendente), imprima el número del Node en la k ^-ésima posición. Si el total de Nodes es < k , imprima -1 .

Ejemplos: 

Entrada: u[] = {0, 0, 1}, v[] = {2, 1, 2}, val[] = {2, 4, 3}, k = 2 
Salida: 
2 
0 
0 
Para 0 Nodes, los Nodes conectados directamente a él son 1 y 2 
con valores 4 y 3 respectivamente, por lo que el Node con el segundo valor más grande es 2. 
Para 1 Node, los Nodes conectados directamente con él son 0 y 2 
con valores 2 y 3 respectivamente, por lo tanto, el Node con El segundo valor más grande es 0. 
Para 2 Nodes, los Nodes conectados directamente a él son 0 y 1 
con valores 2 y 4 respectivamente, por lo que el Node con el segundo valor más grande es 0.

Entrada: u[] = {0, 2}, v[] = {2, 1}, val[] = {2, 4, 3}, k = 2 
Salida: 
-1 
-1 
0 
 

Enfoque: La idea es almacenar los Nodes directamente conectados a un Node junto con sus valores en un vector y clasificarlos en orden creciente, y el k-ésimo valor más grande para un Node, que tiene n número de Nodes directamente conectados a él, será ( n – k) el Node desde el último.

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 print Kth node for each node
void findKthNode(int u[], int v[], int n, int val[], int V, int k)
{
 
    // Vector to store nodes directly
    // connected to ith node along with
    // their values
    vector<pair<int, int> > g[V];
 
    // Add edges to the vector along with
    // the values of the node
    for (int i = 0; i < n; i++) {
        g[u[i]].push_back(make_pair(val[v[i]], v[i]));
        g[v[i]].push_back(make_pair(val[u[i]], u[i]));
    }
 
    // Sort neighbors of every node
    // and find the Kth node
    for (int i = 0; i < V; i++) {
        if (g[i].size() > 0)
            sort(g[i].begin(), g[i].end());
 
        // Get the kth node
        if (k <= g[i].size())
            printf("%d\n", g[i][g[i].size() - k].second);
 
        // If total nodes are < k
        else
            printf("-1\n");
    }
 
    return;
}
 
// Driver code
int main()
{
    int V = 3;
    int val[] = { 2, 4, 3 };
    int u[] = { 0, 0, 1 };
    int v[] = { 2, 1, 2 };
 
    int n = sizeof(u) / sizeof(int);
    int k = 2;
 
    findKthNode(u, v, n, val, V, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// pair class
static class pair
{
    int first,second;
    pair(int a,int b)
    {
        first = a;
        second = b;
    }
}
 
// Function to print Kth node for each node
static void findKthNode(int u[], int v[], int n,
                        int val[], int V, int k)
{
 
    // Vector to store nodes directly
    // connected to ith node along with
    // their values
    Vector<Vector<pair >> g = new Vector<Vector<pair>>();
     
    for(int i = 0; i < V; i++)
    g.add(new Vector<pair>());
 
    // Add edges to the Vector along with
    // the values of the node
    for (int i = 0; i < n; i++)
    {
        g.get(u[i]).add(new pair(val[v[i]], v[i]));
        g.get(v[i]).add(new pair(val[u[i]], u[i]));
    }
 
    // Sort neighbors of every node
    // and find the Kth node
    for (int i = 0; i < V; i++)
    {
        if (g.get(i).size() > 0)
            Collections.sort(g.get(i),new Comparator<pair>()
        {
            public int compare(pair p1, pair p2)
            {
                return p1.first - p2.first;
            }
        });
 
        // Get the kth node
        if (k <= g.get(i).size())
            System.out.printf("%d\n", g.get(i).get(g.get(i).size() - k).second);
 
        // If total nodes are < k
        else
            System.out.printf("-1\n");
    }
 
    return;
}
 
// Driver code
public static void main(String args[])
{
    int V = 3;
    int val[] = { 2, 4, 3 };
    int u[] = { 0, 0, 1 };
    int v[] = { 2, 1, 2 };
 
    int n = u.length;
    int k = 2;
 
    findKthNode(u, v, n, val, V, k);
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Function to print Kth node for each node
def findKthNode(u, v, n, val, V, k):
 
    # Vector to store nodes directly connected
    # to ith node along with their values
    g = [[] for i in range(V)]
 
    # Add edges to the vector along
    # with the values of the node
    for i in range(0, n): 
        g[u[i]].append((val[v[i]], v[i]))
        g[v[i]].append((val[u[i]], u[i]))
 
    # Sort neighbors of every node
    # and find the Kth node
    for i in range(0, V):
        if len(g[i]) > 0:
            g[i].sort()
 
        # Get the kth node
        if k <= len(g[i]):
            print(g[i][-k][1])
 
        # If total nodes are < k
        else:
            print("-1")
      
    return
 
# Driver code
if __name__ == "__main__":
  
    V = 3
    val = [2, 4, 3] 
    u = [0, 0, 1]
    v = [2, 1, 2] 
    n, k = len(u), 2
 
    findKthNode(u, v, n, val, V, k)
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
  
class GFG
{
  
// pair class
class pair
{
    public int first,second;
    public pair(int a,int b)
    {
        first = a;
        second = b;
    }
}
  
class sortHelper : IComparer
{
   int IComparer.Compare(object a, object b)
   {
      pair first = (pair)a;
      pair second = (pair)b;
         
      return first.first - second.first;
   }
}
  
// Function to print Kth node for each node
static void findKthNode(int []u, int []v, int n,
                        int []val, int V, int k)
{
  
    // Vector to store nodes directly
    // connected to ith node along with
    // their values
    ArrayList g = new ArrayList();    
    for(int i = 0; i < V; i++)
        g.Add(new ArrayList());
  
    // Add edges to the Vector along with
    // the values of the node
    for (int i = 0; i < n; i++)
    {
        ((ArrayList)g[u[i]]).Add(new pair(val[v[i]], v[i]));
        ((ArrayList)g[v[i]]).Add(new pair(val[u[i]], u[i]));
    }
  
    // Sort neighbors of every node
    // and find the Kth node
    for (int i = 0; i < V; i++)
    {
        if (((ArrayList)g[i]).Count > 0)
        {
            ArrayList tmp = (ArrayList)g[i];
            tmp.Sort(new sortHelper());
            g[i] = tmp;           
        }
  
        // Get the kth node
        if (k <= ((ArrayList)g[i]).Count)
            Console.Write(((pair)((ArrayList)g[i])[((ArrayList)g[i]).Count - k]).second+"\n");
  
        // If total nodes are < k
        else
            Console.Write("-1\n");
    }
    return;
}
  
// Driver code
public static void Main(string []args)
{
    int V = 3;
    int []val = { 2, 4, 3 };
    int []u = { 0, 0, 1 };
    int []v = { 2, 1, 2 };
    int n = u.Length;
    int k = 2;
    findKthNode(u, v, n, val, V, k);
}
}
  
// This code is contributed by Pratham76

<script>
 
// Javascript implementation of the approach
 
// Function to print Kth node for each node
function findKthNode(u, v, n, val, V, k)
{
     
    // Vector to store nodes directly
    // connected to ith node along with
    // their values
    var g = Array.from(Array(V), () => Array());
 
    // Add edges to the vector along with
    // the values of the node
    for(var i = 0; i < n; i++)
    {
        g[u[i]].push([val[v[i]], v[i]]);
        g[v[i]].push([val[u[i]], u[i]]);
    }
 
    // Sort neighbors of every node
    // and find the Kth node
    for(var i = 0; i < V; i++)
    {
        if (g[i].length > 0)
            g[i].sort();
 
        // Get the kth node
        if (k <= g[i].length)
            document.write(
                g[i][g[i].length - k][1] + "<br>");
 
        // If total nodes are < k
        else
            document.write("-1<br>");
    }
    return;
}
 
// Driver code
var V = 3;
var val = [ 2, 4, 3 ];
var u = [ 0, 0, 1 ];
var v = [ 2, 1, 2 ];
var n = u.length;
var k = 2;
 
findKthNode(u, v, n, val, V, k);
 
// This code is contributed by rutvik_56
 
</script>

2
0
0

Complejidad temporal: O(N)
Espacio auxiliar: O(N)