图中每个顶点都有权的第k个最重相邻节点-yiteyi-C++库

给定一个正数 K 和一个无向的 N 节点，编号从0到N-1，每个节点都有与其关联的权重。请注意，这与每个边都有权重的普通加权图不同。对于每个节点，如果我们按降序对直接连接到它的节点进行排序（根据它们的权重），那么节点的数量是多少 kth 位置打印每个节点的第k个节点编号（不是重量），如果不存在，则打印-1。 例如：

null

Input : N = 3, k = 2, wt[] = { 2, 4, 3 }.edge 1: 0 2edge 2: 0 1edge 3: 1 2Output : 2 0 0Graph:         0 (weight 2)        /        /         1-----2(weight 4)  (weight 3)For node 0, sorted (decreasing order) nodesaccording to their weights are node 1(weight 4),node 2(weight 3). The node at 2nd position fornode 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 fornode 2 is node 0.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

其思想是根据相邻节点的权重对每个节点的邻接列表进行排序。首先，为所有节点创建邻接列表。现在，对于每个节点，直接连接到它的所有节点都存储在一个列表中。在邻接列表中，存储节点及其权重。现在，对于每个节点，按相反顺序对直接连接到它的所有节点的权重进行排序，然后打印每个节点列表中第k个位置的节点号。以下是该方法的实施：

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.*;                       
           
                         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.                       
           
                         # PrKth 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                       

输出：

2 0 0

本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章