不用vector的STL实现

好的，以下是不使用vector的STL实现的代码：

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

const int MAXN = 100000;

int graph[MAXN][10];
bool visited[MAXN];

int dfs(int v, int max_id) {
    visited[v] = true;
    max_id = max(max_id, v);
    for (int i = 0; i < 10; i++) {
        int w = graph[v][i];
        if (w == -1) break;
        if (!visited[w]) {
            max_id = max(max_id, dfs(w, max_id));
        }
    }
    return max_id;
}

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

    // 初始化邻接表
    memset(graph, -1, sizeof(graph));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u-1][i%10] = v-1;
    }

    // 对每个点进行DFS
    for (int i = 0; i < n; i++) {
        memset(visited, false, sizeof(visited));
        int max_id = dfs(i, i);
        cout << max_id+1 << ' ';
    }

    return 0;
}

这里使用了一个二维数组来表示邻接表，时间复杂度和空间复杂度同样为O(nm)。注意到题目中m≤10^5，因此将邻接表的长度限制在10以内对于时间和空间的优化是可行的。