为什么我的代码显示超出时间限制？

Question

今天在leetcode上做题的时候，我在一个运行时间为O(N)的有向图上应用了dfs，但是我的代码给出了TLE，所以在尝试了太多次之后我查看了评论并且有一个接受的代码也在 O(N) 上运行。所以现在我很困惑为什么我的代码没有被接受并且超过了时间限制。我的代码：-

public:
    int ans=INT_MIN;
    vector<vector<int>> gr;
    void dfs(int head, int time, vector<int> inform){
        if(gr[head].size()==0) {ans=max(ans,time);return;}
        for(auto next:gr[head]){
            dfs(next, inform[head]+time, inform);
        }
    }
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        gr.resize(n);
        for(int i=0 ; i<n ; i++){
            if(manager[i]!=-1) gr[manager[i]].push_back(i);
        }
        dfs(headID,0, informTime);
        return ans;
    }

接受的代码之一：-

    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int res = 0;
        for (int i = 0; i < n; ++i)
            res = max(res, dfs(i, manager, informTime));
        return res;
    }

    int dfs(int i, vector<int>& manager, vector<int>& informTime) {
        if (manager[i] != -1) {
            informTime[i] += dfs(manager[i], manager, informTime);
            manager[i] = -1;
        }
        return informTime[i];
    }

如果有人需要问题link:- https://leetcode.com/problems/time-needed-to-inform-all-employees/

Answer 1

在您的 dfs() 函数中，您按值传递 inform，这意味着编译器会在您每次调用该函数时复制 inform，而不是 inform本身。

您应该改为通过引用传递。

void dfs(int head, int time, vector<int> &inform)

为什么我的代码显示超出时间限制？

Why my code is giving Time Limit Exceeded?

c++

coding-style

graph

depth-first-search

data-structures