RunTime Error на DFS задаче C++

313
25 сентября 2017, 03:25

Первый раз написав решение этой задачи на привычном себе питоне, натолкнулся на ошибку 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;
}

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

Answer 1

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

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

поменяйте на

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

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

READ ALSO
Как поймать сигнал переопределенного QGraphicsPixmapItem в слот главного окна?

Как поймать сигнал переопределенного QGraphicsPixmapItem в слот главного окна?

Есть кастомный QGraphicsView, в нем отлавливаю эвенты мыши, чтобы скалировать и панарамировать изображениеВ QGraphicsScene лежит кастомный QGraphicsPixmapItem,...

273
Как удалить последний из тегов с одинаковыми id?

Как удалить последний из тегов с одинаковыми id?

На странице есть несколько тегов с одинаковым id (так получилось)Как при помощи jQuery удалить последний тег?

282
jquery функция $

jquery функция $

Подскажите, что это за способ вызова функции $ и как он работает?

258
Поиск внешних ссылок в JQuery

Поиск внешних ссылок в JQuery

Объясните, пожалуйста, дураку, почему этот код не работает:

260