Допустим, у меня есть DAG и упорядоченный набор ребер, которые я хочу добавить к нему.Очевидно, что добавление определенных ребер может нарушить свойство DAG, поэтому я просто пропускаю такое.
Моя проблема заключается в том, как решить, важен ли порядок этого набора дополнительных ребер (т.е. его можно изменить, чтобы сделать окончательный выводотличается) или нет.
Простой алгоритм состоит в том, чтобы сначала попытаться добавить каждое ребро и удалить все, что привело бы к циклу.Затем добавьте все оставшиеся;в случае какого-либо пропуска порядок важен, иначе нет(Это потому, что первое ребро должно быть принято, а любое позднее пропущенное ребро может быть помещено первым и добавлено).
Это правильно?Можно ли сделать это умнее?