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++
// 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
// 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
# 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+"\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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA