Given a positive number k and an undirected graph of N nodes, numbered from 0 to N-1, each having a weight associated with it. Note that this is different from a normal weighted graph where every edge has a weight.
For each node, if we sort the nodes (according to their weights), which are directly connected to it, in decreasing order, then what will be the number of the node at the kth position. Print kth node number(not weight) for each node and if it does not exist, print -1.
Examples:
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.
The idea is to sort Adjacency List of each node on the basis of adjacent node weights.
First, create Adjacency List for all the nodes. Now for each node, all the nodes which are directly connected to it stored in a list. In adjacency list, store the nodes along with their weights.
Now, for each node sort the weights of all nodes which are directly connected to it in reverse order, and then print the node number which is at kth position in the list of each node.
Below is implementation of this approach:
C++
// 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
// Java program to find Kth node weight after s // sorting of nodes directly connected to a node. import java.util.*; public 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
# 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 |
C#
// C# program to find Kth node weight after s // sorting of nodes directly connected to a node. using System; using System.Collections.Generic; class GFG { // pair class public class pair { public int first, second; public 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(List<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++) { adj[i].Sort((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].Count >= k) Console.Write(adj[i][adj[i].Count - k].second + " "); else Console.Write("-1"); } } // Driven Program 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. List<pair>[] adj = new List<pair>[n + 1]; for (int i = 0; i < n + 1; i++) adj[i] = new List<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); } } |
Javascript
// JavaScript 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. function printkthnode(adj, wt, n, k) { // Sort Adjacency List of all // node on the basis of its weight. for (let i = 0; i < n; i++) { adj[i].sort(); } // Printing Kth node for each node. for (let i = 0; i < n; i++) { if (adj[i].length >= k) { console.log(adj[i][adj[i].length - k][1] + " "); } else { console.log("-1 "); } } } // Driver Code function main() { let n = 3; let k = 2; let wt = [2, 4, 3]; // Making adjacency list, storing // the nodes along with their weight. let adj = new Array(n + 1); for (let i = 0; i <= n; i++) { adj[i] = []; } adj[0].push([wt[2], 2]); adj[2].push([wt[0], 0]); adj[0].push([wt[1], 1]); adj[1].push([wt[0], 0]); adj[1].push([wt[2], 2]); adj[2].push([wt[1], 1]); printkthnode(adj, wt, n, k); } // call the main function main(); // This code is contributed by sanjanasikarwar24 |
Output
200
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
