0

Первый раз написав решение этой задачи на привычном себе питоне, натолкнулся на ошибку TimeLimit, деваться некуда - переписал на С++, и теперь, на 15-м тесте натыкаюсь на RunTime. Собственно вот код:

#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;
}

Заранее спасибо за помощь.

1 ответ 1

1

в функции DFS этот for (r=0; r<=n; r++)

цикл делает одну лишнюю итерацию выходя за рамки как graph так и массива visited - непонятно почему вы там поставили знак равно !?

поменяйте на

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

так как индексация с нуля, значит последний элемент будет под номером n - 1

2
  • 1
    Эх, а я искал как раз что-то подобное у себя в коде, спасибо, глупая ошибка. 23 сен 2017 в 14:37
  • Кстати, 15-й тест прошел, но уперся я во все тот же TimeLimit) Вероятно, где-то зацикливается 23 сен 2017 в 14:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.