TLE求调 思想缩点

fa是并查集 p表示每个点属于哪个分量 cnt是分量数量 l是点之间的路 g是分量之间的路 in是每个分量包含的点 f是最终答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
int a[N];

int fa[N],p[N],cnt;
void init() {
	for(int i=1; i<=n; i++)fa[i]=i;
	return;
}
int find(int x) {
	return (fa[x]==x)?x:fa[x]=find(fa[x]);
}

int f[N];
vector<int>in[N];
vector<int>l[N];
vector<int>g[N];
signed main() {
	cin>>n>>m;
	for(register int i=1; i<=n; i++)cin>>a[i];
	init();
	while(m--) {
		int x,y;
		cin>>x>>y;
		if(a[x]==a[y])fa[find(x)]=find(y);
		else if(a[x]<a[y])l[x].push_back(y);
		else l[y].push_back(x);
	}

	for(register int i=1; i<=n; i++) {
		if(!p[find(i)])p[find(i)]=++cnt;
		p[i]=p[find(i)];
		in[p[i]].push_back(i);
//		cout<<p[i]<<" ";
	}
//	cout<<endl;

	for(register int i=1;i<=cnt;i++) {
//		cout<<"+"<<endl;
		for(register int j=0;j<in[i].size();j++) {
			int u=in[i][j];
//			cout<<u<<endl;
			for(register int k=0;k<l[u].size();k++)g[i].push_back(p[l[u][k]]);
		}
	}
	
	queue<int>q;
	q.push(p[1]);
	f[p[1]]=1;
	while(q.size()) {
		int x=q.front();
		q.pop();
//		cout<<x<<" "<<f[x]<<endl;
		for(register int i=0;i<g[x].size();i++) {
			int y=g[x][i];
			f[y]=max(f[y],f[x]+1);
			q.push(y);
		}
	}
	cout<<f[p[n]]<<endl;
	return 0;
}

提交链接

（感觉没有问题，不知道为啥TLE