The first time I wrote a solution to this problem on a familiar Python, I ran into a TimeLimit error, I have nowhere to go - I rewrote C ++, and now, on the 15th test, I stumble upon Runtime. Actually here is the code:

#include <iostream> #include <vector> using namespace std; int i, j; void DFS(int st, int n, vector<vector<int>> &graph, bool visited[]) { int r; visited[st]=true; for (r=0; r<=n; r++) if ((graph[st][r]!=0) && (!visited[r])) DFS(r, n, graph, visited); } int main() { int n; cin >> n; bool *visited=new bool[n]; vector<vector<int>> graph(n, vector<int>(n, 0)); for(i=0; i<n; i++){ int x; cin >> x; if(x>0){ graph[x-1][i] = 1; } } for (i=0; i<n; i++) { visited[i]=false; } bool *vis=new bool[n]; int outlist[n]; for(i=0;i<n;i++){ int s = 0; DFS(i,n, graph, visited); for(j=0;j<n;j++){ if(visited[j] == true){ s++; } visited[j] = false; } outlist[i] = s; } int max = 0; int maxi; for(i=0; i<n; i++){ if(outlist[i] > max) { max = outlist[i]; maxi = i+1; } } cout << maxi << " " << max; return 0; }

Thanks in advance for your help.

    1 answer 1

    in the DFS function this for (r=0; r<=n; r++)

    the loop does one extra iteration, going beyond both the graph and the visited array - it is not clear why you put the equal sign there!?

    change to

    for (r=0; r < n; r++)

    since indexing from zero, then the last element will be n - 1

    • one
      Eh, and I was looking for just something similar in my code, thanks, stupid mistake. - Alexander Kurmazov
    • By the way, the 15th test was passed, but I rested on the very same TimeLimit) Probably getting stuck somewhere - Alexander Kurmazov