История изменений
Исправление den73, (текущая версия) :
Дуболомность способа в данном случае состоит в том, что не используется антисимметричность. Плюс, в моём случае заданы только вершины, а не рёбра, поэтому заполнение матрицы смежности требует N^2 сравнений, и уже сразу получается матрица достижимости. Плюс нельзя строить инкрементно, при изменении (например, при удалении ребра) всё нужно переделывать заново. Так что свою частную задачу я вроде решил, но в целом тема не раскрыта. Возможно, по ссылкам, к-рые тут накидали, приведены хорошие алгоритмы - я этого не проверял.
Исправление den73, :
Дуболомность способа в данном случае состоит в том, что не используется антисимметричность. Плюс, в моём случае заданы только вершины, а не рёбра, поэтому заполнение матрицы смежности требует N^2 сравнений, и уже сразу получается матрица достижимости. Так что свою частную задачу я вроде решил, но в целом тема не раскрыта. Возможно, по ссылкам, к-рые тут накидали, приведены хорошие алгоритмы - я этого не проверял.
Исходная версия den73, :
Дуболомность способа в данном случае состоит в том, что не используется антисимметричность. Плюс, в моём случае заданы только вершины, а не рёбра, поэтому заполнение матрицы смежности требует N^2 сравнений, и уже сразу получается матрица достижимости. Так что свою частную задачу я вроде решил, но в целом тема не раскрыта.