И снова здравствуйте...

А что Вам про это говорили на лекциях?...

All_ex доброго вечера, ничего так как их не было.

В смысле?... дали задание и решайте... или Вы для самообразования?...
Ну, на практике... в методичках...

И попутный вопрос... А чем Вам не понравился предыдущий вариант решения через степени матрицы смежности?...

Запускаете DFS
Создаёте новый граф `G^(-1)` (меняете напрявления рёбер)
Запускаете DFS на обратном графе вершыны в порядке обратном выходу из них первого DFS
каждое дерево в полученом лесу это связанный компонент

konetz, объясните мне в порядке самообразования, что значит Запускаете DFS...

DFS это алгоритм обхода графа в качестве результата возвращает путь из исходных вершин во все вершины которые из них можно достичь

konetz, ну, про алгоритм слышал... только такого названия не знал...
Это хорошо когда программу написал, а комп посчитал...Но я понял, что roni7 нужно проделать всё это руками... вот в чём проблема...

этот алгоритм выполняеться за линейное время пройтись один раз по каждой вершине и каждой грани (не займёт много времени)

А как принято оформлять на бумажке такой алгоритм?...

All_ex начитки как таковой не было - выдали задание и удачи.
по методу решения: не совсем понял его и из приведенного вами источника мало информации по решению всего задания.

konetz это выполняет программа, без вывода хода решения, а нужно решение "вручную"

roni7 начитки как таковой не было - выдали задание и удачи. - Понял... извините за излишнюю иронию...
Я понял, что это по времени терпит... на днях чуть станет посвободнее со временем, тогда попробую оформить вариант решения...

All_ex, ну учитывая что другие способы я не особо помню а этот точно не скоро забуду и при понимание работы алгоритма не особо сложно
нужно 2 масива d(время входа в вершину) и f(выход) начнём с вершины "1"

` [("vertex" , 1, 2, 4, 6, 3, 5, 7, 8, 9,10), (d,1 , 2 , 3 , 4 , 6 , 7, 13 , 15 , 17 , 19),(f ,12, 11, 10 , 5 , 9, 8, 14 , 16 , 18, 20)]`
разворачиваем грани графа
обходим вершыны в обратном порядке массива f
`[("vertex ", 10, 9 , 8, 7 , 1, 4, 2, 5 , 3 , 6),(d, 1, 3, 5, 7, 9 , 10, 11 , 12 ,13 , 14),(f, 2 , 4 , 6, 8, 20,19, 18, 17, 16, 15)]`

получаем [10], [9], [8], [7], [123456]

konetz, будьте столь любезны, объясните для roni7 чуть подробнее как заполняются массивы...
читать дальшеНу, вот видимо и не придётся самому разбираться до конца... уже помогли...

konetz как я понимаю это и есть решение по нахождению связных компонентов. Можно поподробней описать операции над массивом и принцип его создания.

All_ex как вы говорили самообразоние с целью самосовершенствования никто не отменял, так что может еще будет шанс, да и наверно это не весь ответ.

алгоритм рекурсивный
есть 2 массива d- внего мы вписываем время когда мы первый раз посещаем какуе-то вершину вначале например вершина "1" d[1]=1 из "1" мы переходим в любую вершину в которой ещё не были например "2" вписываем время пребытия d[2]=2, оттуда в 4 d[4]=3, оттуда в "6" d[6]=4, оттуда в "3" d[3]=5 , оттуда в "5" d[5]=6
оттуда мы можем пойти в 2,4 и 6 но там мы уже были поэтому здесь нам больше не чего делать записываем время выхода (массив f) f[5]=7 и возвращаемся к предыдущей вершине если есть куда пойти(в данном случае нет) то идём туда в противном случае выходим и из неё. когда выходим из вершины "1" выбираем любую другую вершину в которой ещё не были и продолжаем. Если были везде то заканчиваем алгоритм.

при втором проходе по графу нужно выбирать вершины не лишбы как а в соответсвии с убыванием велечин в массиве f оставшемся от первого прохода по графу.

я вас обманул мне показалось что есть грань из "6" в "3" это должно выглядеть так :

есть 2 массива d- внего мы вписываем время когда мы первый раз посещаем какуе-то вершину вначале например вершина "1" d[1]=1 из "1" мы переходим в любую вершину в которой ещё не были например "2" вписываем время пребытия d[2]=2, оттуда в 4 d[4]=3, оттуда в "6" d[6]=4, оттуда в "3" d[3]=5 , оттуда в "5" d[5]=6
оттуда мы можем пойти в 2,4 и 6 но там мы уже были поэтому здесь нам больше не чего делать записываем время выхода (массив f) f[5]=7 и из "6" идти не куда записываем время выхода f[6]=5, возвращаемся в "4" идём в "3" d[3]=6, идём в 5 d[5]=7 оттуда мы можем пойти в 2,4 и 6 но там мы уже были поэтому здесь нам больше не чего делать записываем время выхода (массив f) f[5]=8 ивозвращаемся к предыдущей вершине если есть куда пойти(в данном случае нет) то идём туда в противном случае выходим и из неё. когда выходим из вершины "1" выбираем любую другую вершину в которой ещё не были и продолжаем. Если были везде то заканчиваем алгоритм.


и 6 это отдельный связный компонент (в предыдущем посте таже ошибка)

получаем [10], [9], [8], [7], [123456] выходит это и есть базы?

что такое d и f и по какому принципу вы вывели получаем [10], [9], [8], [7], [123456]

по поводу хода составления массива пока разбираюсь.

я же написал что ошибся не [10], [9], [8], [7], [123456] а [10], [9], [8], [7], [12345] [6] не базы а связные компоненты
правельно будет вот так
`[("vertex ", 10, 9 , 8, 7 , 1, 4, 2, 5 , 3 , 6), (d, 1, 3, 5, 7, 9 , 10, 11 , 12 ,13 , 19), (f, 2 , 4 , 6, 8, 18,17, 16, 15, 14, 20)]`
смотрите на время входа в следующую вершину (массив d) если оно больше времени выхода из предыдущей (массив f) то это уже другой связанный компонент

Пример DFS
Полный алгоритм

а как тогда находятся базы?

более менее разобрался получилось:
1-2-3-4-5 → 6 ← 7 ← 8 ← 9 ← 10
как теперь из полученого выразить структуру организации (комитет, коалиция, руководитель), там чтото про висячие вершины идет, из этого получается что все упирается в 1-2-3-4-5.

какие идеи?