k-ésimo Node adyacente más pesado en un gráfico donde cada vértice tiene peso

Dado un número positivo k y un gráfico no dirigido de N Nodes, numerados de 0 a N-1, cada uno con un peso asociado. Tenga en cuenta que esto es diferente de un gráfico ponderado normal donde cada borde tiene un peso.

Para cada Node, si clasificamos los Nodes (según sus pesos), que están directamente conectados a él, en orden decreciente, ¿cuál será el número del Node en la posición k-ésima ? Imprima el número de Node kth (no el peso) para cada Node y, si no existe, imprima -1.

Ejemplos: 

Input : N = 3, k = 2, wt[] = { 2, 4, 3 }.
edge 1: 0 2
edge 2: 0 1
edge 3: 1 2

Output : 2 0 0
Graph:
         0 (weight 2)
        / \
       /   \
      1-----2
(weight 4)  (weight 3)

For node 0, sorted (decreasing order) nodes
according to their weights are node 1(weight 4),
node 2(weight 3). The node at 2nd position for
node 0 is node 2.
For node 1, sorted (decreasing order) nodes 
according to their weight are node 2(weight 3), 
node 0(weight 2). The node at 2nd position for 
node 1 is node 0.
For node 2, sorted (decreasing order) nodes 
according to their weight are node 1(weight 4),
node 0(weight 2). The node at 2nd position for
node 2 is node 0.

La idea es ordenar la lista de adyacencia de cada Node en función de los pesos de los Nodes adyacentes. 

Primero, cree una lista de adyacencia para todos los Nodes. Ahora, para cada Node, todos los Nodes que están directamente conectados a él se almacenan en una lista. En la lista de adyacencia, almacene los Nodes junto con sus pesos.
Ahora, para cada Node, clasifique los pesos de todos los Nodes que están directamente conectados a él en orden inverso, y luego imprima el número de Node que está en la posición k en la lista de cada Node.

A continuación se muestra la implementación de este enfoque: 

// C++ program to find Kth node weight after s
// sorting of nodes directly connected to a node.
#include<bits/stdc++.h>
using namespace std;
 
// Print Kth node number for each node after sorting
// connected node according to their weight.
void printkthnode(vector< pair<int, int> > adj[],
                        int wt[], int n, int k)
{
    // Sort Adjacency List of all node on the basis
    // of its weight.
    for (int i = 0; i < n; i++)
      sort(adj[i].begin(), adj[i].end());
 
    // Printing Kth node for each node.
    for (int i = 0; i < n; i++)
    {
        if (adj[i].size() >= k)
          cout << adj[i][adj[i].size() - k].second;
        else
          cout << "-1";
    }
}
 
// Driven Program
int main()
{
    int n = 3, k = 2;
    int wt[] = { 2, 4, 3 };
 
    // Making adjacency list, storing the nodes
    // along with their weight.
    vector< pair<int, int> > adj[n+1];
 
    adj[0].push_back(make_pair(wt[2], 2));
    adj[2].push_back(make_pair(wt[0], 0));
 
    adj[0].push_back(make_pair(wt[1], 1));
    adj[1].push_back(make_pair(wt[0], 0));
 
    adj[1].push_back(make_pair(wt[2], 2));
    adj[2].push_back(make_pair(wt[1], 1));
 
    printkthnode(adj, wt, n, k);
    return 0;
}

// Java program to find Kth node weight after s
// sorting of nodes directly connected to a node.
import java.util.*;
 
class GFG
{
    // pair class
    static class pair
    {
        int first, second;
 
        pair(int a, int b)
        {
            first = a;
            second = b;
        }
    }
 
    // Print Kth node number for each node after sorting
    // connected node according to their weight.
    static void printkthnode(Vector<pair> adj[], int wt[], int n, int k)
    {
        // Sort Adjacency List of all node on the basis
        // of its weight.
        for (int i = 0; i < n; i++)
            Collections.sort(adj[i], new Comparator<pair>()
            {
                public int compare(pair p1, pair p2)
                {
                    return p1.first - p2.first;
                }
            });
 
        // Printing Kth node for each node.
        for (int i = 0; i < n; i++)
        {
            if (adj[i].size() >= k)
                System.out.print(adj[i].get(adj[i].size() -
                                            k).second + " ");
            else
                System.out.print("-1");
        }
    }
 
    // Driven Program
    public static void main(String[] args)
    {
        int n = 3, k = 2;
        int wt[] = { 2, 4, 3 };
 
        // Making adjacency list, storing the nodes
        // along with their weight.
        Vector<pair>[] adj = new Vector[n + 1];
        for (int i = 0; i < n + 1; i++)
            adj[i] = new Vector<pair>();
 
        adj[0].add(new pair(wt[2], 2));
        adj[2].add(new pair(wt[0], 0));
 
        adj[0].add(new pair(wt[1], 1));
        adj[1].add(new pair(wt[0], 0));
 
        adj[1].add(new pair(wt[2], 2));
        adj[2].add(new pair(wt[1], 1));
 
        printkthnode(adj, wt, n, k);
    }
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find Kth node
# weight after sorting of nodes
# directly connected to a node.
 
# Print Kth node number for each node
# after sorting connected node
# according to their weight.
def printkthnode(adj, wt, n, k):
     
    # Sort Adjacency List of all
    # node on the basis of its weight.
    for i in range(n):
        adj[i].sort()
 
    # Printing Kth node for each node.
    for i in range(n):
        if (len(adj[i]) >= k):
            print(adj[i][len(adj[i]) -
                             k][1], end = " ")
        else:
            print("-1", end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    n = 3
    k = 2
    wt = [2, 4, 3]
 
    # Making adjacency list, storing
    # the nodes along with their weight.
    adj = [[] for i in range(n + 1)]
 
    adj[0].append([wt[2], 2])
    adj[2].append([wt[0], 0])
 
    adj[0].append([wt[1], 1])
    adj[1].append([wt[0], 0])
 
    adj[1].append([wt[2], 2])
    adj[2].append([wt[1], 1])
 
    printkthnode(adj, wt, n, k)
 
# This code is contributed by PranchalK

200

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.