$AC~Code$

#include <bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) 
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, a[MAXN];
vector<int> e[MAXN];
void dfs(int u, int d)
{
	if (a[u])
		return ;
	a[u] = d;
	for (int i = 0; i < e[u].size(); i++)
		dfs(e[u][i], d);
}
int main()
{
	IOS;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		e[v].push_back(u);
	}
	for (int i = n; i; i--)
		dfs(i, i);
	for (int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}

本题也可算是图论经典题了。

思路

如果暴力dfs很显然会超时。我们可以反向建边，对于一个较大的点 $x$，我们可以遍历所有它能到达的点，那么这些点的答案都是 $x$，除非它已经有了更大的答案。

但如果单纯是这样仍会超时，我们要从 $n$ 开始从大到小遍历，这样如果一个点有了答案就一定是最大的。

最后从 $1$ 到 $n$ 输出答案即可，时间复杂度为 $O(n)$。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;
ll n,m,ans[N];
vector<ll> vec[N];
void dfs(ll x,ll fa){
    if(ans[x])
        return;
    ans[x]=fa;
    for(auto i=vec[x].begin();i!=vec[x].end();i++)
        dfs(*i,fa);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1,u,v;i<=m;i++)
        scanf("%lld%lld",&u,&v),vec[v].push_back(u); // 反向建边
    for(ll i=n;i>=1;i--)
        dfs(i,i);
    for(ll i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    return 0;
}