Всем привет! Нигде не могу найти как посчитать количество простых цепей длины L(или просто найти все простые цепи). Нашел только это, но как я понимаю для N = 100, этот способ в 4 секунды не уложится. Сам смог додуматься только до запуска dfs из каждой вершины и для каждого пути передать свой массив used:
void dfs(short int st, short int dist, vector<bool> used) {
if (dist >= 7) {//В моей задаче нужно найти кол-во простых цепей длины 7
++ans;
return;
}
for (auto r : g[st]) {
if (!used[r]) {
used[r] = 1;
dfs(r, dist + 1, used);
used[r] = 0;
}
}
}
Спасибо за помощь!
