Какими способами улучшить решение через BST?
Я решил задачу по подсчету элементов на конкретном уровне(расстоянии) от корня графа. Вполне понимаю что мое решение можно и нужно улучшить. Не могли бы вы посоветовать какие конкретные вещи стоит оптимизировать в моем коде?
using namespace std;
int num = 0;
vector<int> graph[100000];
int countLevel(const int lvl, const int root) {
queue<int> q;
int level[100000] = {0};
bool visited[100000] = {0};
int cnt = 0;
q.push(root);
level[root] = 1;
visited[root] = 1;
while (q.size() != 0) {
int current = q.front();
q.pop();
if (level[current] == lvl)
cnt++;
if (level[current] > lvl)
break;
for (int i = 0; i < graph[current].size(); i++) {
if (!visited[graph[current][i]]) {
q.push(graph[current][i]);
level[graph[current][i]] = level[current] + 1;
visited[graph[current][i]] = 1;
}
}
}
return cnt;
}
int main() {
cin >> num;
for(int i = 1; i < num; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int level;
cin >> level;
cout << countLevel(level, 1);
}
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Ну здесь реализован поиск в ширину (BFS, а не BST), принципиально быстрее ничего нет.
Вот только зачем продолжать работу, если достигнут уровень lvl?
Сразу после cnt++; нужно переходить к следующей итерации цикла, не вызывая for для данного узла.
if (level[current] == lvl)
cnt++;
else
for...