You are given an undirected graph consisting of N vertices, numbered from 1 to N, and...

 

Transcribed Image Text:

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K]. Your task is to assign all values from the range [1.N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal. For example, given N = 5, A = [2, 2, 1, 2], B = [1, 3, 4, 4], the graph has four edges: (2, 1), (2, 3), (1, 4), (2, 4). In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). 5, val=1 1, val=3 7 2, val=5 3, val=2 9. 4, val=4 This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 +9 = 31: This way we obtain the sum of values at all edges' endpoints equal to 7 + 8+7+9 = 31: edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3) edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1) edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4) edge (2, 4): 9 = 5 (vertex 2) + 4 (vertex 4) Notice that the value assigned to vertex 5 did not have any effect on the final result as it is not an endpoint of any edge. Write a function: You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K]. Your task is to assign all values from the range [1.N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal. For example, given N = 5, A = [2, 2, 1, 2], B = [1, 3, 4, 4], the graph has four edges: (2, 1), (2, 3), (1, 4), (2, 4). In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). 5, val=1 1, val=3 7 2, val=5 3, val=2 9. 4, val=4 This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 +9 = 31: This way we obtain the sum of values at all edges' endpoints equal to 7 + 8+7+9 = 31: edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3) edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1) edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4) edge (2, 4): 9 = 5 (vertex 2) + 4 (vertex 4) Notice that the value assigned to vertex 5 did not have any effect on the final result as it is not an endpoint of any edge. Write a function:

Answer rating: 100% (QA)

Java Code public class Main public static void mainS... View the full answer