Нахождение всех циклов в ориентированном графе обходом вглубину через матрицу смежности
Похожий вопрос был на хабре, даже с алгоритмом, но все-таки нужна помощь с обходом графа и поиском циклов. Имеется такой граф:
Алгоритм находит только простые циклы, а как найти другие?. (Например,такой 982341289) Подскажите, как модифицировать код. Код:
void dfs(int v, int start){
if(used[v]){
if(v == start) {
for (int i = 0; i < path.size(); ++i)
cout << path[i] << " ";
cout << v << endl;
}
return;
}
used[v] = 1;
path.push_back(v);
for(int i = 0; i < graph[v].size(); ++i)
if(graph[v][i] == 1)
dfs(i, start);
used[v] = 0;
path.pop_back();
}
int main() {
graph.push_back({ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }); //0
graph.push_back({ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 }); //1
graph.push_back({ 0, 0, 0, 1, 0, 1, 0, 0, 1, 0 }); //2
graph.push_back({ 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 }); //3
graph.push_back({ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 }); //4
graph.push_back({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }); //5
graph.push_back({ 0, 0, 0, 1, 0, 1, 0, 1, 0, 0 }); //6
graph.push_back({ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 }); //7
graph.push_back({ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 }); //8
graph.push_back({ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }); //9
for(int i = 0; i < 10; i++) {
used.resize(10, 0);
dfs(i, i);
//path.clear();
}
return 0;
}
