Problem Description

You are given a directed acyclic graph (DAG) with n nodes and m edges. The nodes are numbered from 1 to n. Each node i has an associated weight w_i.

For any path in the graph, you can obtain a sequence of node weights based on the order of traversal. The goal is to find the maximum possible length of a Longest Non-Decreasing Subsequence (LNDS) among all such sequences derived from all possible paths in the graph.

Note: Given a sequence S, its Longest Non-Decreasing Subsequence S' is a subsequence of S where S' is non-decreasing (i.e., each element is less then or equal to the next) and has the maximum possible length among all such subsequences.

Example: For the sequence S = [11, 12, 13, 9, 8, 17, 19], the LNDS is S' = [11, 12, 13, 17, 19] with a length of 5.

Input Format

• The first line contains two positive integers n and m, representing the number of nodes and edges.
• The second line contains n positive integers A_1, A_2, ..., A_n, representing the weights of nodes 1 to n.
• The next m lines each contain two positive integers u_i and v_i, indicating a directed edge from node u_i to node v_i.

Output Format

Output a single integer representing the answer.

Sample Input #1

5 4
2 10 6 3 1
5 2
2 3
3 1
1 4

Sample Output #1

3

Sample Input #2

6 11
1 1 2 1 1 2
3 2
3 1
5 3
4 2
2 6
3 6
1 6
4 6
1 2
5 1
5 4

Sample Output #2

4

Sample Input #3

6 11
5 9 10 5 1 6
5 4
5 2
4 2
3 1
5 3
6 1
4 1
4 3
5 1
2 3
2 1

Sample Output #3

4

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ m ≤ 10^5
• 1 ≤ A_i ≤ 10

Solution Approach

This problem combines graph theory and dynamic programming. Since the graph is a Directed Acyclic Graph (DAG), we can process nodes in topological order to ensure that when we process a node, all its predecessors have been processed.

A naive DP approach would define dp[i] as the length of the LNDS ending at node i. However, updating this for each edge would lead to O(n*m) complexity, which is too slow.

A key observation is the constraint 1 ≤ A_i ≤ 10. This allows us to use a more efficient state representation.

We define dp[node][value] as the length of the longest non-decreasing subsequence achievable on a path ending at node, where the last element of the subsequence is exactly value.

State Transitions: For an edge (u -> v):

1. Append: We can append node v's weight to a subsequence ending at u. This is only valid if the last value in the subsequence at u is less than or equal to A[v]. dp[v][A[v]] = max(dp[v][A[v]], dp[u][last_val] + 1) for all last_val ≤ A[v].
2. Inherit: We can also choose not to use v's weight in the subsequence, simply carrying forward the best subsequence from u. This means for all possible ending values val (1 to 10), we can take the maximum from u. dp[v][val] = max(dp[v][val], dp[u][val]) for all val from 1 to 10.

We perform these updates for all edges while traversing nodes in topological order.

The final answer is the maximum value found in the entire dp table.

Complexity Analysis

• Time Complexity: O((n + m) * K), where K = 10 (the maximum possible weight). The topological sort runs in O(n + m), and for each edge, we perform O(K) operations for the two types of updates.
• Space Complexity: O(n * K) for the DP table.

Implementation

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 1e5 + 5;
const int MAX_WEIGHT = 10;

int nodeWeight[MAX_NODES];
int inDegree[MAX_NODES];
int dp[MAX_NODES][MAX_WEIGHT + 1]; // dp[node][last_value]
vector<int> graph[MAX_NODES];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int numNodes, numEdges;
    cin >> numNodes >> numEdges;

    for (int i = 1; i <= numNodes; ++i) {
        cin >> nodeWeight[i];
    }

    for (int i = 0; i < numEdges; ++i) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
        inDegree[to]++;
    }

    queue<int> topoQueue;
    // Initialize DP and topological queue
    for (int node = 1; node <= numNodes; ++node) {
        if (inDegree[node] == 0) {
            topoQueue.push(node);
        }
        // A path consisting of only this node has LNDS length 1 ending with its own weight.
        dp[node][nodeWeight[node]] = 1;
    }

    while (!topoQueue.empty()) {
        int currentNode = topoQueue.front();
        topoQueue.pop();

        for (int nextNode : graph[currentNode]) {
            inDegree[nextNode]--;
            if (inDegree[nextNode] == 0) {
                topoQueue.push(nextNode);
            }

            // Transition 1: Append nextNode's weight to a valid subsequence from currentNode
            for (int lastVal = 1; lastVal <= nodeWeight[nextNode]; ++lastVal) {
                dp[nextNode][nodeWeight[nextNode]] = max(dp[nextNode][nodeWeight[nextNode]],
                                                         dp[currentNode][lastVal] + 1);
            }

            // Transition 2: Carry forward the best subsequence without using nextNode's weight
            for (int val = 1; val <= MAX_WEIGHT; ++val) {
                dp[nextNode][val] = max(dp[nextNode][val], dp[currentNode][val]);
            }
        }
    }

    int answer = 0;
    for (int node = 1; node <= numNodes; ++node) {
        for (int val = 1; val <= MAX_WEIGHT; ++val) {
            answer = max(answer, dp[node][val]);
        }
    }

    cout << answer << '\n';
    return 0;
}