思路缩点

#include<bits/stdc++.h>
using namespace std;
int n,m,a[200005],ca[200005],cnum,to[200005],ed[200005],ans[200005];
vector<int>con[200005],cs[200005],ccon[200005];
bool vis[200005];queue<int>q;

void dfs1(int u){
	vis[u]=true;
	cs[cnum].push_back(u);to[u]=cnum;
	for(int v:con[u])if(!vis[v] && a[v]==a[u])dfs1(v);
	return ;
}

int read(){
	char c;
	while(!isdigit(c=getchar()));
	int res=(c^48);
	while(isdigit(c=getchar()))res=(res<<3)+(res<<1)+(c^48);
	return res;
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	while(m--){
		int u=read(),v=read();
		con[u].push_back(v);
		con[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(!vis[i])cnum++,dfs1(i),ca[cnum]=a[cs[cnum][0]];
	for(int i=1;i<=cnum;i++){
		map<int,bool>mp;
		for(int u:cs[i])for(int v:con[u])
			if(!mp[to[v]] && ca[i]<ca[to[v]])ed[i]++,ccon[to[v]].push_back(i),mp[to[v]]=true;
	}
	ans[to[n]]=1;
	q.push(to[n]);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int v:ccon[x]){
			ans[v]=max(ans[v],ans[x]+1);
			if(!(--ed[v]))q.push(v);
		}
	}
	printf("%d",ans[to[1]]);
	return 0;
}