"В моей интерпретации простые числа — это независимые оси многомерного пространства, а составные — адреса, возникающие из произведений по этим осям.
Вы сейчас другими словами сказали, что все составные числа однозначно раскладываются на произведение простых.
На числовой прямой такие произведения образуют покрытие: составные адреса заняты, а в пределах доказанной безопасной границы пустоты соответствуют простым. Каждое новое простое добавляет ось и расширяет возможности покрытия"
Вы строите какое-то подмножество составных чисел. Оно у вас гарантированно покрывает все составные числа до безопасной границы. Добавляя новое простое число в рассмотрение вы расширяете ваше множество определенным способом. Показываете, что безопасная граница смещается.
Или в терминах решета - вычеркиваете числа из таблицы, в пределах безопасной границы вы вычеркнули все числа. Потом вычеркиваете еще какие-то числа. Никаких "миров" и покрытий не надо. Все отлично объясняется в общепринятых терминах.
Я хочу перейти от привычного расположения чисел на одной прямой к дискретной многомерной картине
Перемудрили. Ну вот раскладывается каждое число однозначно на простые множители. Вы хоть как-то где-то используете, что у вас многомерное пространство, или просто смотрите на разложение чисел на простые? Если вы не используете геометрию пространства, т.е. расстояния в вашем пространстве, то зря только переусложняете.
а покрытие — их отображением на числовую прямую
Ну вот вы просто работаете с числами. Получаете множетсво составных с какими-то свойствами. В этих стандартных терминах и рассуждайте.
Адрес» действительно является числом — словом я подчёркиваю его положение в покрытии
Но покрытие - оно же на числовой прямой уже и есть.
Адреса? Это же просто числа? Зачем усложнять. Используйте термин "число", вы же их вычеркиваете.
Опора - вроде понятно, но ясно, что это не математический объект, а термин из алгоритма. Когда будет виден алгоритм, станет понятнее. Это просто простое число, а интерес оно вызывает только тем, что оно используется в алгоритме.
Конечный мир - вообще непонятно. Вот есть ограничения на произведения. Как из них получается мир? Надо расписать. Я догадываюсь, что это множество чисел, порожденных произведениями каких-то чисел.
Любое определение должно быть в виде: "Бяка - это бука, которая обладает вот такими свойствами". При чем к этому моменту у вас бука уже должна быть точно так же определена, или это какой-то стандартный математический объект - число, множество, функция, матрица, или что-то еще. Вы должны задать класс объекта и его свойства. "Задается произведениями" не объясняет ничего читателю. Я могу задать произведениями множество чисел, длины сторон многоугольника, функцию и счет в ресторане.
Вспышка - опять термин из алгоритма. На самом деле он не нужен. Ну вот просто алгоритм обрабатывает числа до какого-то. На следующей итерации до какого-то другого. И вот эти последние числа в итерациях образуют последовательность, свойства которой вы исследуете. Ну называйте это последовательностью чисел обработанных на каждой итерации. Определите ее в виде - это последнее число, обработанное алгоритмом 1 на итерации цикла i. Специальный термин тут не нужен и смысла читателю не несет. Можете алгоритм назвать вcпышковым, потому что вам его поведение напоминает вспышки. Почему не прыжки, кстати? Но смысла вводить термин я не вижу. Это лишь нагружает текст и путает читателей.
Спасибо. Раз уж у вас алгоритм получился, да еще и в 400 раз быстрее, то сформулируйте пожалуйста обязательно, что за задачу он решает (поиск всех простых до N? Проверки, что N простое? Поиск максимального простого до N?) и приведите сам алгоритм.
Обязательно дайте формальные определения вашим понятиям. Что такое мир. Это множество составных чисел, построенных специальным образом? Оформляйте в виде (пример): Мир для опоры B - это множество чисел . Фактически это составные числа до B^2, имеющие делитель до B включительно.
Лемма 1.3: содержит все простые до и только их. Иными словами, пропустки в мире (тени) до упомянутой границы содержат все простые числа и только их.
Не стесняйтесь математических формул, раз уж вы "сложный" уровень материала поставили. Тут серъезные люди, математические формулы они поймут гораздо лучше условного "При простой опоре B мир строится из произведений". Хабр умеет нативно отображать формулы на латехе - стандарте среди ученых математиков.
Начало с тенями и вспышками по-моему описывает тупо сегментированное решето. В чем вообще отличие-то? Вы там утверждаете, что ускорили в 350-400 раз, но что именно сделали у вас не описано вообще. И что вы там вообще считали написано весьма туманно и нечетко.
Вот зачем вы все термины переименовали?
Ваша тень - это тупо вычеркивание в решете. Опора - простое число. Вспышка - область со всеми составными уже вычеркнутыми. Поскольку у каждого составного числа N есьт делитель не больше sqrt(N), то ясно как определять границы "вспышки" - это квадрат от максимального использованого делителя.
А еще у вас куча нигде неопределенных терминов. Базисы, миры, что у вас за правила. Ужасно статья написана, ничего непонятно. Могли бы ваш ИИ попросить помочь вам и статью оформить, они хоть и галлюционируют иногда, но мысли излагают гораздо лучше и последовательнее этого.
Вы тут своим ИИ-психозом делитесь, а вы пробовали пустому чату скормить ваш опус с промтом покритиковать и опровергнуть? Если ИИ специально не просить, то оно всегда будет нахваливать, так уж его натренировали.
Я бы не верил этим числам и прогнозам. В отличии от других технологий, эта пока лишь приносит их хозяевам многомиллиардные убытки. На прибыль они выйдут ой как не скоро. И то, если остановят производство новых моделей, но чертова конкуренция не дает это сделать. Когда инвесторских денег станет не хватать, цена пойдет вверх.
// nextBalancedSequence transforms the parenthesis slice in-place to the lexicographically next valid one.
// Returns true if a next sequence exists, or false if the current sequence is already the last one.
func nextBalancedSequence(s []byte) bool {
n := len(s)
balance := 0
// 1. Scan from right to left to find the first '(' that can be replaced by ')'
for i := n - 1; i >= 0; i-- {
if s[i] == '(' {
balance--
} else {
balance++
}
// A '(' can be replaced if moving right-to-left yields a positive balance of closing brackets
if s[i] == '(' && balance > 0 {
s[i] = ')'
balance--
// 2. Greedily fill the remaining positions to maintain the lexicographically smallest valid suffix
remLen := n - 1 - i
openCount := (remLen - balance) / 2
closeCount := remLen - openCount
idx := i + 1
for j := 0; j < openCount; j++ {
s[idx] = '('
idx++
}
for j := 0; j < closeCount; j++ {
s[idx] = ')'
idx++
}
return true
}
}
return false
}
// GenerateAllParentheses generates all valid parenthesis strings for n pairs in lexicographical order.
func GenerateAllParentheses(n int) []string {
if n <= 0 {
return []string{}
}
// Start with the lexicographically first valid sequence: n '(' followed by n ')'
current := make([]byte, 2*n)
for i := 0; i < n; i++ {
current[i] = '('
current[n+i] = ')'
}
var result []string
for {
// Append a copy of the current valid string state
result = append(result, string(current))
// Find the next lexicographical sequence in-place
if !nextBalancedSequence(current) {
break
}
}
return result
}
Можно написать компактнее, но так понятнее идея.
Если решаете задачи на литкоде, то наверняка встречали задачу о перестановках и знакомы с алгоритмом Нарайаны.
Многие комбинаторные объекты можно генерировать похожим образом. Начните с самой лексикографически минимальной строки, потом каждый раз меняйте ее минимальным способом, чтобы получить следующую лексикографически строку. Это надо поменять самый правый символ на чуть больший в алфавите так, чтобы потом строку можно было достроить до валидной. Так же тут. Начните со строки (((((...))))).
Вот что можно поменять в строке, чтобы она стала дальше в словаре? Первый измененный символ должен быть "(", замененный на ")". Обратная замена сделает строку меньше лексикографически. Чтобы эта замена была корректной, баланс (количество незакрытых пока скобок) перед этим символом должен быть больше 0, иначе ")" уйдет в минус. Чтобы изменение было минимально, надо взять самый правый такой символ. Дальше надо достроить строку до минимальной - взяв сначала все "(", потом все ")". Очевидно, что такая строка будет валидной.
Вот пример: начали мы с ((())). Самый правый (, который не на нулевом уровне, это третий символ. Заменив его мы получаем (() и надо оставшиеся скобочки жадно поставить: получаем (()()). Если хотим опять получить следующую строку, самый правый (, который можно заменить - опять третий. Получаем начало (()), дополняем: (())(). Теперь уже третий ( нельзя заменять, он никуда не вложен, заменив второй, получим ()(()).
Это удобно реализовывать проходом с конца. вы знаете сколько всего скобочек, вы можете вычитать увиденные скобки из этого и вы получаете, сколько там слева открытых и закрытых. Разница их количеств - это баланс. Первый (, который встретили, и левее его открывающих больше, чем закрывающих заменяйте на ), потом известные количества ( и ) ставьте и все. Это 2 вложенных цикла.
Работает это так же быстро, как самый оптимизированный рекурсивный перебор с отсечениями. У вас отсечений в рекурсии нет, но можно же глядя на баланс понять, можно ли тут ставить ")" или "(" в рекурсии и никогда не доходить до конца с ненулевым балансом.
Правильное рассуждение выводится из определения в условии. Или у вас n-1 скобка внутри новой пары. Или у вас сначала комбинация из k пар, неразрывная, а потом комбинация из n-k пар. Чтобы первая была неразрывная, она должна быть обрамлена парой скобок. Или еще логичнее: любая комбинация из n скобок - это (), внутри которой комбинация из 0<=k<=n пар скобок, а потом комбинация из n-k-1 скобок.
Потому что в отличии от ИИшных компаний, которые вываливают мегабайты слопа для хайпа и поднятия капитализации как можно быстрее, математикам надо статью хорошо и понятно оформить, перепроверить и отправить в рецензируемый журнал. Это очень долго и медленно. Уже готовая и почти оформленная идея может и пару лет вылезать на свет. Журналы не круглый год принимают статьи, рецензирование идет долго, могут быть несколько раундов исправлений замечаний. Просто вываливать свои работы куда-то в интернет весьма некрасиво.
Про эту галочку надо знать. Очень многие даже не догадываются. Ну не пишут при открытии чата большим буквами "внимание, все что вы тут напишите - может быть использовано нами как угодно. Интеллектуальная собственность, секреты, приватная и личная информация - все будет принадлежать нам". Проинформирован о ней чувак мог бы быть только если бы нашел ее случайно в настройках или вдумчиво и внимательно прочитал все N-цать страниц privacy policy, написанных отборным юридическим канцеляритом, который нормальные люди прочитать и осознать могут весьма с трудом.
Потом, корпорации любят периодически эти галочки сбрасывать к дефолтному состоянию. Ходи потом доказывай, что ты ее ставил.
OpenAI сперли (может, нечаянно) решение про Навье-Стокса. ИИшечка была нартенирована на неопубликованных заметках ученого и "придумала" очень похожие идеи.
Очень глупая логическая ошибка. Это доказательство от противного.
Вы допустили, что простых конечное число, получили, что или есть числа близнецы, не входящие в это конечное множество простых чисел, или есть какие-то другие простые числа не входящие в это конечное множество простых чисел. Противоречие, да. Значит предположение, что простых чисел конечно - не верно. Вы тут никак не доказали ничего про простых близнецов. Вам для этого надо начать с предположения, что простых близнецов конечное количество и там прийти к противоречию.
Для раскраски в минимальное количество цветорв надо делать перебор с откатом. Реализовывать алгоритм из теореммы о 4 красках будет сложновато.
Какая-нибудь жадность может с большой вероятностью найти хорошую раскраску.
Если же подходит не самый оптимальный варинат, то можно весьма просто гарантировать 5 цветов, взяв школьное доказательство теоремы о 5 красках (или факт из статьи): Берем любую вершину v степени <= 5 (а она всегда есть), удаляем из графа, красим оставшейся граф рекурсивно. Добавляем вершину назад. если у нее было <= 4 соседей, или 5 соседей не все разного цвета, то тупо красим новую вершину каким-то допустимым цветом из 5. Иначе пусть цвета вдоль графа (в порядке обхода по углу) a,b,c,d,e. Тогда запустим обход в глубину от вершины цвета a чередуясь a-c. Если не дошли до соседа новой вершины цвета c, то можно всю обйденную компоненту перекрасить a<->с и освободить себе цвет a. если же дошли, то тогда точно так же можно обойти с вершины цвета b чередуя b-d или b-e, ведь путь v->a->..->c->v на плоскости отрезает вершину цвета b от вершин d, e.
Если граф планарен, но не нарисован на плоскости, т.е. мы не знаем обход по углу, то можно перебрать 10 пар цветов и попробовать перекрасить кадого соседа в каждый другой цвет. Если dfs не вернулся к новой вершине, то перекраска возможна. Фактически мы перебираем, в какой цвет красим новую вершину, и в какой цвет красим конфликтного соседа.
Это работает за O(n^2). Можно сделать даже не рекурсивно, сначала находим порядок добавления новых вершин, потом перекрашиваем. Dfs можно заменить на Bfs.
Вы сейчас другими словами сказали, что все составные числа однозначно раскладываются на произведение простых.
Вы строите какое-то подмножество составных чисел. Оно у вас гарантированно покрывает все составные числа до безопасной границы. Добавляя новое простое число в рассмотрение вы расширяете ваше множество определенным способом. Показываете, что безопасная граница смещается.
Или в терминах решета - вычеркиваете числа из таблицы, в пределах безопасной границы вы вычеркнули все числа. Потом вычеркиваете еще какие-то числа. Никаких "миров" и покрытий не надо. Все отлично объясняется в общепринятых терминах.
Перемудрили. Ну вот раскладывается каждое число однозначно на простые множители. Вы хоть как-то где-то используете, что у вас многомерное пространство, или просто смотрите на разложение чисел на простые? Если вы не используете геометрию пространства, т.е. расстояния в вашем пространстве, то зря только переусложняете.
Ну вот вы просто работаете с числами. Получаете множетсво составных с какими-то свойствами. В этих стандартных терминах и рассуждайте.
Но покрытие - оно же на числовой прямой уже и есть.
Новую статью на днях прочитаю, дам отзыв.
Адреса? Это же просто числа? Зачем усложнять. Используйте термин "число", вы же их вычеркиваете.
Опора - вроде понятно, но ясно, что это не математический объект, а термин из алгоритма. Когда будет виден алгоритм, станет понятнее. Это просто простое число, а интерес оно вызывает только тем, что оно используется в алгоритме.
Конечный мир - вообще непонятно. Вот есть ограничения на произведения. Как из них получается мир? Надо расписать. Я догадываюсь, что это множество чисел, порожденных произведениями каких-то чисел.
Любое определение должно быть в виде: "Бяка - это бука, которая обладает вот такими свойствами". При чем к этому моменту у вас бука уже должна быть точно так же определена, или это какой-то стандартный математический объект - число, множество, функция, матрица, или что-то еще. Вы должны задать класс объекта и его свойства. "Задается произведениями" не объясняет ничего читателю. Я могу задать произведениями множество чисел, длины сторон многоугольника, функцию и счет в ресторане.
Вспышка - опять термин из алгоритма. На самом деле он не нужен. Ну вот просто алгоритм обрабатывает числа до какого-то. На следующей итерации до какого-то другого. И вот эти последние числа в итерациях образуют последовательность, свойства которой вы исследуете. Ну называйте это последовательностью чисел обработанных на каждой итерации. Определите ее в виде
- это последнее число, обработанное алгоритмом 1 на итерации цикла i. Специальный термин тут не нужен и смысла читателю не несет. Можете алгоритм назвать вcпышковым, потому что вам его поведение напоминает вспышки. Почему не прыжки, кстати? Но смысла вводить термин я не вижу. Это лишь нагружает текст и путает читателей.
Спасибо. Раз уж у вас алгоритм получился, да еще и в 400 раз быстрее, то сформулируйте пожалуйста обязательно, что за задачу он решает (поиск всех простых до N? Проверки, что N простое? Поиск максимального простого до N?) и приведите сам алгоритм.
Обязательно дайте формальные определения вашим понятиям. Что такое мир. Это множество составных чисел, построенных специальным образом? Оформляйте в виде (пример):
.
Мир для опоры B - это множество чисел
Фактически это составные числа до B^2, имеющие делитель до B включительно.
Лемма 1.3:
содержит все простые до 
и только их. Иными словами, пропустки в мире (тени) до упомянутой границы содержат все простые числа и только их.
Не стесняйтесь математических формул, раз уж вы "сложный" уровень материала поставили. Тут серъезные люди, математические формулы они поймут гораздо лучше условного "При простой опоре B мир строится из произведений". Хабр умеет нативно отображать формулы на латехе - стандарте среди ученых математиков.
Начало с тенями и вспышками по-моему описывает тупо сегментированное решето. В чем вообще отличие-то? Вы там утверждаете, что ускорили в 350-400 раз, но что именно сделали у вас не описано вообще. И что вы там вообще считали написано весьма туманно и нечетко.
Вот зачем вы все термины переименовали?
Ваша тень - это тупо вычеркивание в решете. Опора - простое число. Вспышка - область со всеми составными уже вычеркнутыми. Поскольку у каждого составного числа N есьт делитель не больше sqrt(N), то ясно как определять границы "вспышки" - это квадрат от максимального использованого делителя.
А еще у вас куча нигде неопределенных терминов. Базисы, миры, что у вас за правила. Ужасно статья написана, ничего непонятно. Могли бы ваш ИИ попросить помочь вам и статью оформить, они хоть и галлюционируют иногда, но мысли излагают гораздо лучше и последовательнее этого.
Вы тут своим ИИ-психозом делитесь, а вы пробовали пустому чату скормить ваш опус с промтом покритиковать и опровергнуть? Если ИИ специально не просить, то оно всегда будет нахваливать, так уж его натренировали.
В школу! Переучивать основы! Не позорьтесь
Я бы не верил этим числам и прогнозам. В отличии от других технологий, эта пока лишь приносит их хозяевам многомиллиардные убытки. На прибыль они выйдут ой как не скоро. И то, если остановят производство новых моделей, но чертова конкуренция не дает это сделать. Когда инвесторских денег станет не хватать, цена пойдет вверх.
Как же не запрещал-то?
Задача:
С каких это пор 2i - целое?
Квадраты-то всегда положительные. -2^2 = 4.
Еще есть быстрый нерекурсивный метод.
Код (нейрослоп, ибо я на го не пишу)
Можно написать компактнее, но так понятнее идея.
Если решаете задачи на литкоде, то наверняка встречали задачу о перестановках и знакомы с алгоритмом Нарайаны.
Многие комбинаторные объекты можно генерировать похожим образом. Начните с самой лексикографически минимальной строки, потом каждый раз меняйте ее минимальным способом, чтобы получить следующую лексикографически строку. Это надо поменять самый правый символ на чуть больший в алфавите так, чтобы потом строку можно было достроить до валидной. Так же тут. Начните со строки (((((...))))).
Вот что можно поменять в строке, чтобы она стала дальше в словаре? Первый измененный символ должен быть "(", замененный на ")". Обратная замена сделает строку меньше лексикографически. Чтобы эта замена была корректной, баланс (количество незакрытых пока скобок) перед этим символом должен быть больше 0, иначе ")" уйдет в минус. Чтобы изменение было минимально, надо взять самый правый такой символ. Дальше надо достроить строку до минимальной - взяв сначала все "(", потом все ")". Очевидно, что такая строка будет валидной.
Вот пример: начали мы с ((())). Самый правый (, который не на нулевом уровне, это третий символ. Заменив его мы получаем (() и надо оставшиеся скобочки жадно поставить: получаем (()()). Если хотим опять получить следующую строку, самый правый (, который можно заменить - опять третий. Получаем начало (()), дополняем: (())(). Теперь уже третий ( нельзя заменять, он никуда не вложен, заменив второй, получим ()(()).
Это удобно реализовывать проходом с конца. вы знаете сколько всего скобочек, вы можете вычитать увиденные скобки из этого и вы получаете, сколько там слева открытых и закрытых. Разница их количеств - это баланс. Первый (, который встретили, и левее его открывающих больше, чем закрывающих заменяйте на ), потом известные количества ( и ) ставьте и все. Это 2 вложенных цикла.
Работает это так же быстро, как самый оптимизированный рекурсивный перебор с отсечениями. У вас отсечений в рекурсии нет, но можно же глядя на баланс понять, можно ли тут ставить ")" или "(" в рекурсии и никогда не доходить до конца с ненулевым балансом.
Правильное рассуждение выводится из определения в условии. Или у вас n-1 скобка внутри новой пары. Или у вас сначала комбинация из k пар, неразрывная, а потом комбинация из n-k пар. Чтобы первая была неразрывная, она должна быть обрамлена парой скобок. Или еще логичнее: любая комбинация из n скобок - это (), внутри которой комбинация из 0<=k<=n пар скобок, а потом комбинация из n-k-1 скобок.
Как раз невероятным кажется совпадение, что ИИ-шечка смогла действительно решить только одну задачу, ту наработки о которой он постил в чатик.
По остальным задачам там какие-то подвижки кое где есть, но целиком решений - нет.
Потому что в отличии от ИИшных компаний, которые вываливают мегабайты слопа для хайпа и поднятия капитализации как можно быстрее, математикам надо статью хорошо и понятно оформить, перепроверить и отправить в рецензируемый журнал. Это очень долго и медленно. Уже готовая и почти оформленная идея может и пару лет вылезать на свет. Журналы не круглый год принимают статьи, рецензирование идет долго, могут быть несколько раундов исправлений замечаний. Просто вываливать свои работы куда-то в интернет весьма некрасиво.
Про эту галочку надо знать. Очень многие даже не догадываются. Ну не пишут при открытии чата большим буквами "внимание, все что вы тут напишите - может быть использовано нами как угодно. Интеллектуальная собственность, секреты, приватная и личная информация - все будет принадлежать нам". Проинформирован о ней чувак мог бы быть только если бы нашел ее случайно в настройках или вдумчиво и внимательно прочитал все N-цать страниц privacy policy, написанных отборным юридическим канцеляритом, который нормальные люди прочитать и осознать могут весьма с трудом.
Потом, корпорации любят периодически эти галочки сбрасывать к дефолтному состоянию. Ходи потом доказывай, что ты ее ставил.
Сплагиаченным считается только вот то одно, опубликованное раньше. Эти 100 еще никто не проверял, может там вообще бред.
Мужик работал над задачей, готовил публикацию, по пути использовал chat-gpt для оформления. А он на пользовательских чатах, оказывается, тренируется.
OpenAI сперли (может, нечаянно) решение про Навье-Стокса. ИИшечка была нартенирована на неопубликованных заметках ученого и "придумала" очень похожие идеи.
Очень глупая логическая ошибка. Это доказательство от противного.
Вы допустили, что простых конечное число, получили, что или есть числа близнецы, не входящие в это конечное множество простых чисел, или есть какие-то другие простые числа не входящие в это конечное множество простых чисел. Противоречие, да. Значит предположение, что простых чисел конечно - не верно. Вы тут никак не доказали ничего про простых близнецов. Вам для этого надо начать с предположения, что простых близнецов конечное количество и там прийти к противоречию.
Это математическая задача. Иметь что 4, что 5, что 6 красок - практической разницы почти нет. Но конкретное число - 4 - тут интересно теоретически.
Для раскраски в минимальное количество цветорв надо делать перебор с откатом. Реализовывать алгоритм из теореммы о 4 красках будет сложновато.
Какая-нибудь жадность может с большой вероятностью найти хорошую раскраску.
Если же подходит не самый оптимальный варинат, то можно весьма просто гарантировать 5 цветов, взяв школьное доказательство теоремы о 5 красках (или факт из статьи): Берем любую вершину v степени <= 5 (а она всегда есть), удаляем из графа, красим оставшейся граф рекурсивно. Добавляем вершину назад. если у нее было <= 4 соседей, или 5 соседей не все разного цвета, то тупо красим новую вершину каким-то допустимым цветом из 5. Иначе пусть цвета вдоль графа (в порядке обхода по углу) a,b,c,d,e. Тогда запустим обход в глубину от вершины цвета a чередуясь a-c. Если не дошли до соседа новой вершины цвета c, то можно всю обйденную компоненту перекрасить a<->с и освободить себе цвет a. если же дошли, то тогда точно так же можно обойти с вершины цвета b чередуя b-d или b-e, ведь путь v->a->..->c->v на плоскости отрезает вершину цвета b от вершин d, e.
Если граф планарен, но не нарисован на плоскости, т.е. мы не знаем обход по углу, то можно перебрать 10 пар цветов и попробовать перекрасить кадого соседа в каждый другой цвет. Если dfs не вернулся к новой вершине, то перекраска возможна. Фактически мы перебираем, в какой цвет красим новую вершину, и в какой цвет красим конфликтного соседа.
Это работает за O(n^2). Можно сделать даже не рекурсивно, сначала находим порядок добавления новых вершин, потом перекрашиваем. Dfs можно заменить на Bfs.