图的反向建边+dfs
对于这类从某一点出发,找出能到达的最优解问题,反向建边很好用
反向建边,对于那些第一次到达的点,那么其能到达的的最大点就是反向的出发点
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 100001, M =100001;
int n,m,k;
int h[N],e[M],ne[M],idx;
int ma,now;
bool st[N];
int dist[N];
void add(int a,int b)
{
e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}
void dfs(int x,int y)
{
if(dist[x]) return ;
dist[x]=y;
for(int i=h[x];i!=-1;i=ne[i])
{
dfs(e[i],y);
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
scanf("%d %d",&a,&b);
add(b,a);
}
for(int i=n;i;i--)
{
ma=i;now=i;
dfs(i,i);
}
for(int i=1;i<=n;i++) cout<<dist[i]<<' ';
return 0;
}