小埋学习图之图的遍历 全MLE求助

常规
1 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v[100005];
vector<int> tmp;
bool vis[100005];
int n,m,maxn = -1,ma[100005];
void dfs(int x){
    vis[x] = true;
    tmp.push_back(x);
    maxn = max(maxn,x);
    for (int i = 0;i < v[x].size();i++) if (!vis[v[x][i]]) dfs(v[x][i]);
    vis[x] = false;
}
signed main(){
    cin >> n >> m;
    for (int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1;i <= n;i++)
        if (!vis[i]){
            tmp.clear();
            maxn = 0;
            dfs(i);
            for (int i = 0;i < tmp.size();i++) ma[tmp[i]] = maxn;
        }
    for (int i = 1;i <= n;i++) cout << ma[i] << " ";
    return 0;
}

谢谢大佬们帮本蒟蒻看看!

2

有没有一种可能，你开了100005个vector

3

确实

4

难道不能吗？

5

动态数组不应该就一个v就行了吗？

6

那不就会造成超内存吗

7

我之前没加vis[x] = false;这句是WA 10没有MLE

8

所以能让我看看题面吗

9

D. 小埋学习图之图的遍历

Problem ID: 15633

Contest ID: 5886

必做题

Runtime Error

时间：1s 空间：512M

题目描述：

小埋最近在学习有向图的遍历相关知识，小埋学习过图的遍历的相关方法，可以使用dfs或者bfs来遍历整个有向图，但是小埋发现这个问题有一些不一样，这个图的遍历是问你当前点能够到达的点的最大编号，小埋希望你能帮她解决这个问题。

输入格式：

第一行两个整数一个n一个m，n代表有向图中有n个点，m代表有向图中有m条有向边。

接下来是m条边。

输出格式：

输出每个点能够到达的最大编号

样例1输入：

4 3 1 2 1 3 2 3

样例1输出：

3 3 3 4

数据范围：

1<=n,m<=100000

10

啊，这是邻接表

11

你用邻接矩阵试试？

12

稍等，这道题貌似我以前做过

13

同意，邻接矩阵不行再用动态数组，但是图的问题我还是建议用动态数组，会方便一些

14

邻接矩阵要开100000* 100000更不行了

15

那就动态数组，你会吗？

16

我觉得主要是我回溯的问题，但是不加会Wa10

17

不一定，我看看你的代码，稍等一下

18

我加这句WA10 \rightarrow MLE
vis[x] = false;

19

稍等一下哈

20

好，谢谢