不用STL，并尽可能提高算法效率：Description 此题是上一道题目的数据加强版。 给定 � n个点， � m条边的有向图，对于每个点 � v，求 � ( � ) f(v)表示从点 � v出发能到达的编号最大的点(包括自己在内)。 � , � ≤ 1 0 5 n,m≤10 5 Input Format 第一行有 2 2个整数 � n, � m。 接下来 � m行，每行2个整数 � � , � � u i ​ ,v i ​ ,表示 � � u i ​ 到 � � v i ​ 有一条边。 点用 1 , 2 , ⋯ , � 1,2,⋯,n编号。 Output Format � n个整数 � ( 1 ) , � ( 2 ) , ⋯ , � ( � ) f(1),f(2),⋯,f(n).

好的，下面是不使用STL并尽可能提高算法效率的实现方法。

思路：

我们可以使用邻接表存储图，并使用数组记录从每个点出发能到达的编号最大的点。然后从后向前遍历每个点，利用已经计算出来的结果来更新当前点能到达的编号最大的点。

具体实现：

我们可以定义两个数组，一个用来存储图的邻接表，另一个用来记录从每个点出发能到达的编号最大的点。我们可以使用一个指针数组来实现邻接表，指针数组的每个元素是一个指向链表的指针，链表中存储每个点能够到达的下一个点的编号。同时，我们也需要定义一个数组，用来记录从每个点出发能够到达的最大点的编号，一开始可以将这个数组中的每个元素都设置为当前点的编号。

接下来，我们从后向前遍历每个点，对于每个点，我们遍历它能到达的所有点，并将它们的最大编号更新为当前点的最大编号。这样，当遍历完所有点后，我们就能得到每个点出发能到达的编号最大的点了。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;

// 邻接表中存储从当前点能够到达的下一个点的编号
// next[i]表示从i出发能够到达的下一个点的编号
int next[N], head[N], idx;

// maxn[i]表示从i出发能够到达的最大点的编号
int maxn[N];

// 添加一条有向边
void add(int a, int b){
    next[idx] = head[a];
    head[a] = idx++;
}

int main(){
    int n, m;
    cin >> n >> m;

    // 初始化maxn数组
    for(int i = 1; i <= n; i++){
        maxn[i] = i;
    }

    // 建图
    while(m--){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    // 从后向前遍历每个点
    for(int i = n; i > 0; i--){
        // 遍历当前点能到达的所有点
        for(int j = head[i]; j != -1; j = next[j]){
            int v = next[j];

            // 更新从当前点出发能够到达的最大点的编号
            maxn[i] = max(maxn[i], maxn[v]);
        }
    }

    // 输出结果
    for(int i = 1; i <= n; i++){
        cout << maxn[i] << " ";
    }
    cout << endl;

    return 0;
}

时间复杂度：

在这个实现方法中，我们只需要遍历每个点一次，对于每个点，我们需要遍历它能到达的所有点，并更新它们的最大编号。因此，总时间复杂度为 $\mathcal{O}(m+n)$，其中 $m$ 表示边数，$n$ 表示点数。