Можно ли решить задачу без использования бинарного поиска?

Да, существует подход к решению задачи минимизации максимальной степени исходящих вершин в неориентированном графе без использования бинарного поиска. Однако он может быть не столь очевидным, как алгоритм с бинарным поиском по значению максимальной степени, и может потребовать более тщательной проработки. 

Вот один из возможных подходов для решения задачи за O(g(n)), где g(n) — это время работы алгоритма максимального потока:

1. **Соберите сеть потока:** Преобразуйте ваш граф в сеть потока. Для каждой вершины графа создайте два узла: входной (u_in) и выходной (u_out). Затем добавьте ребро с пропускной способностью 1 от u_in до u_out для каждой вершины u. Это ребро будет ограничивать максимальную степень исходящих рёбер для данной вершины.

2. **Направление рёбер:** Если у вас есть ребро между вершинами v и u в исходном графе, вы можете направить его от v к u. Представьте это как добавление ребра от v_out к u_in в вашей сети, также с пропускной способностью 1.

3. **Определение максимальной степени:** Теперь, чтобы минимизировать максимальную степень исходящих рёбер, вам нужно настроить граф так, чтобы максимальная степень (число исходящих рёбер) для любой вершины не превышала некоторого предела D. Это достигается путём ограничения потока в сетевой модели (например, рёбра, соединяющие выходные узлы, могут быть ограничены).

4. **Максимальный поток:** Теперь задача сводится к нахождению максимального потока в данной сети с учётом установленных ограничений на максимальную степень. Подпорки и управления потоками могут быть настроены для предотвращения превышения максимального лимита D.

Таким образом, если вы сможете решить задачу о максимальном потоке в вашей сети, то это позволит вам определить, возможно ли направить рёбра так, чтобы максимальная степень исходящих рёбер не превышала D. 

Этот процесс может быть выполнен за O(g(n)), так как вы используете один раз алгоритм максимального потока, не прибегая к бинарному поиску. Однако стоит учитывать, что ключевым моментом здесь является умение корректно сформулировать требование на ограничение максимальной степени в терминах сетей потоков. 

Таким образом, хотя у вас уже есть решение, использующее бинарный поиск, вы можете попробовать найти решение, использующее только один алгоритм максимального потока, что может упростить и ускорить ваш подход.

Именно max flow, а не mincostmaxflow? Потому что есть очевидное решение с mincostmaxflow. 
 
 Граф почти такой же. Раздвоенное ребро. В середину каждого ребра вход из истока пропускной способностью 1 и стоимостью 0. Вдоль ребра в обе стороны такие же ребра - пропускной способности 1 и стоимости 0. Из вершины делаем degree(v) ребер в сток. Каждое пропускной способностью 1 и прогрессивно увеличивающимися стоимостями. Первые ребра стоимостью 1. Вторые - n+1, сделующие (n+1)^2 и т.д. 
 
 Стоимость полного потока будет тем меньше, чем меньше максимальная степень, ведь даже одно ребро стоимостью (n+1)^k для вершины степени k+1 хуже чем если бы все вершины имели степень k и ответ был бы n*(n+1)^(k-1). 
 
 Если нужен именно просто поток, а не минимальной стоимости, то возможно можно изменить алгоритм потока, чтобы искать его итеративно для всех возможных значений x в вашем графе. Ведь алгоритм итерационно ищет дополняющий путь в остаточной сети. И ответ для x можно использовать в качестве стартового потока для задачи с x+1. Т.е не надо логарифм раз запускать поток для разных графов, а после выполнения увеличить пропускные сопособности нужных ребер на 1 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.