Problem: Given a weighted bidirectional graph with N nodes and M edges and all the weights as distinct positive numbers, find the maximum number of edges that can be visited on traversing the graph such that the weights are ascending.

Solution: When a weighted edge is encountered in an ascending order between nodes, say u and v, it must be the first edge of the path starting at either u or v and no other nodes. In addition, that path starts at one vertex, goes through edge uv and then the remaining longest ascending path up to the other vertex. Therefore, the weights accumulated at both these nodes is the maximum of (w[u], w[v] + 1) and (w[v], w[u]+1) in an array w of weights of longest ascending paths starting at that vertex.

 

public static int solution_unique_weights(int N, int[] src, int[] dest, int[] weight) {

            int M = weight.length;

            int[] e = new int[N];

            Integer[] index = new Integer[M];

            for (int i = 0; i <M; i++) { index[i] = i; }

            Comparator<Integer> comparator = (i, j) -> weight[j] - weight[i];

            Arrays.sort(index, 0, M, comparator);

            for (int I = 0; i< M; i++) {

                          int u = src[index[i]];

                          int v = dest[index[i]];

                           int count = Math.max(Math.max(e[u], e[v] + 1), Math.max(e[v], e[u]+1));

                           e[u] = count;

                           e[v] = count;

             }

             return Arrays.stream(e).max().getAsInt();

    }

 

    src[0] = 0    dest[0] = 1    weight[0] = 4

    src[1] = 1    dest[1] = 2    weight[1] = 3

    src[2] = 1    dest[2] = 3    weight[2] = 2

    src[3] = 2    dest[3] = 3    weight[3] = 5

    src[4] = 3    dest[4] = 4    weight[4] = 6

    src[5] = 4    dest[5] = 5    weight[5] = 7

    src[6] = 5    dest[6] = 0    weight[6] = 9

    src[7] = 3    dest[7] = 2    weight[7] = 8

    index:  0 1 2 3 4 5 6 7  // before sort

    index:  2 1 0 3 4 5 7 6  // after sort

    e: 

    0  1  0  1  0  0  0  0

    0  2  2  1  0  0  0  0

    3  3  2  1  0  0  0  0

    3  3  3  4  4  0  0  0

    3  3  3  4  5  5  0  0

    3  3  4  4  5  5  0  0

    6  3  4  4  5  6  0  0