0

I'm working on a algorithm problem, and it discribed as follows:

Suppose the deep learning model is a directed acyclic graph. If operator A depends on the output of operator B, then A can be calculated after the execution of B. If there is no dependency relation, then A can be executed in parallel. Given N nodes, the information of each node contains the execution time of the node and the list of the next nodes, and the shortest execution time of the neural network is calculated. The node index starts at 0.

and here is the input example:

7
A 10 1 2 3
B 9 4 5 6
C 22
D 20
E 19
F 18
G 21

Here is my solution:

#include <bits/stdc++.h>
using namespace std;

int dfs(int nodeTime, const vector<int>& nextNodes, vector<vector<int>> NN){
    // Check whether the children of the current node have children
    bool is_end = true;
    for (int node : nextNodes) {
        if (NN[node][1] != 0){
            is_end = false;
            break;
        }
    }

    //The children of the current node have no children, find the maxTime
    if (is_end) {
        int maxTime = 0;
        for (int node : nextNodes) {
            maxTime = max(node, maxTime);
        }
        return nodeTime + maxTime;
    }

    //some children of the current node have children, keep doing dfs()
    else{
        int maxTime = 0;
        for (int nodeIdx : nextNodes) {
            if (NN[nodeIdx].size() != 1){
                vector<int> next;
                next.assign(NN[nodeIdx].begin() + 1, NN[nodeIdx].end());
                maxTime = max(maxTime, dfs(NN[nodeIdx][0], next, NN));
            }
            else maxTime = max(maxTime, NN[nodeIdx][0]);
        }
        return maxTime + nodeTime;
    }
}

int str_int(const string& s){
    char c[10];
    strcpy(c, s.c_str());
    return atoi(c);
}

int main() {
    // input stage
    int n;
    cin >> n;
    vector<vector<int>> NN;
    vector<int> temp;
    vector<string> stemp;
    string s;
    for (int i = 0; i < n; ++i) {
        stemp.clear();
        temp.clear();
        while (cin >> s){
            stemp.push_back(s);
            if (getchar() == '\n') break;
        }
        for (int j = 1; j < stemp.size(); ++j) {
            temp.push_back(str_int(stemp[j]));
        }
        NN.push_back(temp);
    }

   
    vector<int> initialNextNodes; //Initialize the sequence of children of the starting node
    initialNextNodes.assign(NN[0].begin() + 1, NN[0].end());
    int res = dfs(NN[0][0], initialNextNodes, NN);
    cout << res;
    return 0;
}

The right output is 40, Debug mode gives the right answer, but Run mode gives the wrong answer, I can't figure out what went wrong. I looked up the common causes of this error, probably a pointer being used without space allocated, or a variable being used without an initial value assigned. But these do not seem to be the answer to my question, can anyone help me? I would be so grateful.

  • 4
    [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) And [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Some programmer dude Sep 08 '22 at 11:47
  • 3
    And different behavior between a "debug" and a "release" build (or similar concepts), typically indicated *undefined behavior*. Add lots of debug output to see values of variables and calculations at different times in the program. – Some programmer dude Sep 08 '22 at 11:50
  • 4
    Code that changes behaviour (in your case, observable output) when compiled with different optimisation settings (e.g. "Debug" versus "Release") is often a hint to the presence of undefined behaviour. With more aggressive optimisation, the compiler takes more liberties in reorganising the code, and that increases likelihood of symptoms. Stepping through with a debugger won't necessarily work to isolate the problem - try adding bounds checking everywhere in your code (particularly array indices) you can. – Peter Sep 08 '22 at 11:51
  • 3
    Start by enabling as many compiler warnings as you can (`-Wall -Wextra -Werror` is a good *start* with `g++`). Then *fix* all the warnings. Then enable undefined behaviour sanitizer and fix what it finds. Then try enabling address sanitizer and fix what it finds. You can also try running `clang-tidy` over your code and fix what it points out. – Jesper Juhl Sep 08 '22 at 12:00
  • 1
    This is due to a bug in the shown code from an out of bounds array access. If you replace ***every*** occurence of the subscript operator, `[]`, with `at()`, an exception will be thrown, and you can figure out the bug all by yourself. – Sam Varshavchik Sep 08 '22 at 12:05
  • A difference between Debug Mode and Release Mode should be expected, especially execution times. Verify the optimization settings for the Release Mode. – Thomas Matthews Sep 08 '22 at 16:59

0 Answers0