洛谷题面
感觉有点毒瘤，不过还是有些 trick 在的。
题意翻译（复制于洛谷题面）：
给定一个 \(N\) 个点 \(M\) 条无向边的图，图上每个点都有其颜色。求所有经过点权单调不降的路径中，出现的不同颜色的个数最多是多少。
由于是单调不降的路径，所以可以点权大的点到点权小的点的路径对结果没有影响，可以当有向边连。
点权相同且相连的点可以来回走，对结果没有影响，可以缩成一个点。
这样这张无向图就变成了由点权小的点到点权大的点的 DAG。
建图的时候把所有边先存起来，等用并查集将所有点缩成一个的时候再连边。
然后我们可以在这张图上来计 \(1\) 到 \(N\) 这条路径上不同颜色的个数。
有的题解里用了 Dijkstra 等算法，由于 DAG 的性质所以求解的本质一样，不再赘述。
由于是 DAG，所以可以跑拓扑排序，但是直接 dp 是不对的，有可能变为了以其他点为起点到 \(N\) 的路径。
我们可以将其他点的 dp 值初始化为负无穷，然后 \(1\) 点的 dp 值为 \(1\)，此时进行转移要么是 \(1\) 到 \(N\) 路径的值，要么是负无穷，进行一次判断即可。
代码如下。
#include<bits/stdc++.h>
using namespace std;
template<typename T>
T read(){
T f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return f*x;
}
constexpr int MAXN=2e5+10,MAXM=2e5+10;
int n,m,a[MAXN],fa[MAXN],cnt,head[MAXN],tcnt,dp[MAXN],in[MAXN];
bool vis[MAXN];
struct EDGE1{
int v,nxt;
}edge[MAXM];
struct EDGE2{
int u,v;
}tedge[MAXM];
void add(int u,int v){
edge[++cnt]={v,head[u]};
head[u]=cnt;
++in[v];
}
namespace sol{
int sget(int x){
if(fa[x]==x)return x;
else return fa[x]=sget(fa[x]);
}
void merge(int x,int y){
fa[sget(y)]=sget(x);
}
void solve(){
n=read<int>();m=read<int>();
for(int i=1;i<=n;++i){
a[i]=read<int>();
fa[i]=i;
}
for(int i=1,u,v;i<=m;++i){
u=read<int>();v=read<int>();
if(a[u]==a[v])merge(u,v);
else{
if(a[u]>a[v])swap(u,v);
//a[u]<a[v]
tedge[++tcnt]={u,v};
}
}
for(int i=1;i<=tcnt;++i){
add(sget(tedge[i].u),sget(tedge[i].v));
}
queue<int>q;
for(int i=1;i<=n;++i){
if(!in[sget(i)]){
in[sget(i)]=1;
q.push(sget(i));
}
}
memset(dp,0x80,sizeof(dp));
dp[sget(1)]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
dp[v]=max(dp[u]+1,dp[v]);
--in[v];
if(in[v]==0){
q.push(v);
}
}
}
printf("%d\n",max(dp[sget(n)],0));
}
}
int main(){
sol::solve();
return 0;
}