Первый раз написав решение этой задачи на привычном себе питоне, натолкнулся на ошибку 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;
}
Заранее спасибо за помощь.
в функции DFS
этот
for (r=0; r<=n; r++)
цикл делает одну лишнюю итерацию выходя за рамки как graph
так и массива visited
- непонятно почему вы там поставили знак равно !?
поменяйте на
for (r=0; r < n; r++)
так как индексация с нуля, значит последний элемент будет под номером n - 1
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Есть кастомный QGraphicsView, в нем отлавливаю эвенты мыши, чтобы скалировать и панарамировать изображениеВ QGraphicsScene лежит кастомный QGraphicsPixmapItem,...
На странице есть несколько тегов с одинаковым id (так получилось)Как при помощи jQuery удалить последний тег?