最长不下降子序列Lis.cpp
问题描述
小杨有一个包含n 个节点m 条边的有向无环图，其中节点的编号为1 到n 。
对于编号为i 的节点，其权值为Ai 。对于图中的一条路径，根据路径上的经过节点的先后顺序可以得到一个节点权值的序列，小杨想知道图中所有可能序列中最长不下降子序列的最大长度。
注：给定一个序列S ，其最长不下降子序列S’ 是原序列中的如下子序列：整个子序列S’ 单调不降，并且是序列中最长的单调不降子序列。例如，给定序列 S= [11,12,13,9, 8, 17, 19]，其最长不下降子序列为S’= [11,12,13,17, 19]，长度为5 。
输入描述
第一行包含两个正整数 n,m，表示节点数和边数。第二行包含n个正整数 A1,A2,...,An,表示节点1到n的点权。之后m行每行包含两个正整数ui,vi ，表示第i 条边连接节点ui 和vi，方向为从ui 到vi 。
输出描述
输出一个正整数，表示该图中所有可能序列中最长不下降子序列的最大长度。
样例输入1
5 4
2 10 6 3 1
5 2
2 3
3 1
1 4
样例输出1
3
样例输入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
样例输出2
4
样例输入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
样例输出3
4

数据范围：
30%，n≤10^3有向无环图为一条链,max Ai≤10;
60%，n≤10^5,max Ai≤2;
100%，n≤10^5,max Ai≤10;
对于全部数据，保证有1≤n≤10^5, 1≤m≤10^5, 1≤Ai≤10。