Сейчас: Код ищет количество точек, через которое пройдёт алгоритм для возвращения в исходную позицию
Пометки: граф невзвешенный, ориентированный.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int start;
int n;
cin >> n; // число вершин
cin >> start;
vector <vector <int> > g (n, vector<int>(n, 0)); //матрица смежности
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
int finish;
finish=start;
vector <int> d(n, -1); // массив длин (хранит длину до данной вершины)
d[start-1] = 0;
queue <int> q; // создание очереди из вершин
q.push(start-1); // добавление в очередь точки старта
vector <bool> used(n,false); // буловский массив посещений (true если данная вершина была обработана и false если вершина не обработана)
used[start] = true; // помечаем стартовую вершину, что ее уже посетили
while (!q.empty())
{
int v = q.front();
q.pop();
for (int i = 0; i < n; ++i)
{
int to = g[v][i];
if (!used[i] && (to == 1))
{
used[i] = true;
q.push(i);
d[i] = d[v] + 1;
}
}
}
cout << d[finish-1];
return 0;
}
Можно взять матрицу смежности, и возводить её во вторую, третью и т.д. степень, пока диагональные элементы A[i,i] не станут ненулевыми.
Формулировка неясная, и пока нельзя понять, нужно ли искать количество циклов для каждой вершины, минимальные циклы для одной выбранной вершины или ещё что.
В любом случае диагональный элемент A[i,i] в матрице Ak даёт количество циклов длины k для данной вершины.
Для примера из ссылки куб матрицы показывает, что циклы длиной 3 есть для вершин 3,4,5, а четвертая степень - циклы длиной 4 для вершин 2,3,4,5. В данном примере всех циклов по одному, а вот путей 4-6 длиной три - две штуки
X1 X2 X3 X4 X5 X6
X1 0 0 0 1 0 1
X2 0 0 1 0 0 0
A3= X3 0 0 1 1 0 1
X4 0 0 0 1 1 2
X5 0 1 0 0 1 1
X6 0 0 0 0 0 0
X1 X2 X3 X4 X5 X6
X1 0 0 1 0 0 0
X2 0 1 0 0 1 1
A4= X3 0 1 1 0 1 1
X4 0 0 1 1 0 1
X5 0 0 0 1 1 2
X6 0 0 0 0 0 0
Если мы знаем расстояние, то есть длину кратчайшего пути между вершинами i, j, и оно равно d, то достаточно рассмотреть d-ую степень матрицы смежности графа. Элемент с координатами (i,j) матрицы A^d покажет число путей длины d от i до j; все они являются кратчайшими.
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Найти k1-количество одинаковых элементов в двумерном массиве c++;