Требуется решить следующую задачу, которая вытекает из задачи построения сетевого графика. Дан список меток ребер некоторого ориентированного ациклического графа, их весов, а также ссылок на метки других ребер - в таком случае говорят, что ребро "зависит" от других ребер. Зависимость выражается в следующем - для каждого ребра, от которого зависит данное ребро, существует путь из его конечной вершины в начальную вершину зависимого ребра. Если пути на перечисленных ребрах не существует, то добавляется ребро нулевого веса, такое чтобы путь появился. На граф накладывается условие - в нем ровно одна вершина (исток), в которую не входят ребра и ровно одна вершина (сток), из которой ребра не выходят. Пример исходных данных: https://prnt.sc/mv8x50 Соответствующий примеру граф: https://prnt.sc/mv8xq5 Собственно, задача - построить граф, соответствующий произвольным входным данным (предполагается, что данные удовлетворяют условиям, накладываемым на граф). В примере несложно дойти до построения графа с перечисленными в исходных данных ребрами, но сложность заключается в том, как учесть непрямые связи (ребра $% 2 \rightarrow 3 $%, $%3 \rightarrow 4 $%). Вопрос - как построить такой граф? UPD. Похоже, нашел одно из решений. Считаю, что вопрос можно оставить открытым - возможно, появятся другие интересные идеи. задан 9 Мар '19 2:15 elman |