K-й по величине узел среди всех узлов, напрямую подключенных к данному узлу в неориентированном графе
Даны два массива u и v , представляющие граф такой, что существует неориентированное ребро от u [i] до v [i] (0 ≤ v [i], u [i] <N), и каждый узел имеет некоторое значение val [ i] (0 ≤ i <N). Для каждого узла, если узлы, подключенные напрямую к нему, отсортированы в порядке убывания в соответствии с их значениями (в случае равных значений, отсортируйте его по их индексам в порядке возрастания), выведите номер узла в k- й позиции. Если общее количество узлов <k, выведите -1 .
Примеры:
Input: u[] = {0, 0, 1}, v[] = {2, 1, 2}, val[] = {2, 4, 3}, k = 2
Output:
2
0
0
For 0 node, the nodes directly connected to it are 1 and 2
having values 4 and 3 respectively, thus node with 2nd largest value is 2.
For 1 node, the nodes directly connected to it are 0 and 2
having values 2 and 3 respectively, thus node with 2nd largest value is 0.
For 2 node, the nodes directly connected to it are 0 and 1
having values 2 and 4 respectively, thus node with 2nd largest value is 0.
Input: u[] = {0, 2}, v[] = {2, 1}, val[] = {2, 4, 3}, k = 2
Output:
-1
-1
0
Approach: The idea is to store the nodes directly connected to a node along with their values in a vector and sort them in increasing order, and the kth largest value for a node, having n number of nodes directly connected to it, will be (n – k)th node from last.
Below is the implementation of the above approach:
C++
// 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
" , g[i][g[i].size() - k].second); // If total nodes are < k else printf ( "-1
" ); } 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
// 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
" , g.get(i).get(g.get(i).size() - k).second); // If total nodes are < k else System.out.printf( "-1
" ); } 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
# 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#
// 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+ "
" ); // If total nodes are < k else Console.Write( "-1
" ); } 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 |
2 0 0
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.