497
правок
Изменения
→Шаг 5: удаление двойных дуг
=== Шаг 5: удаление двойных дуг ===
Разбираемся с двойными дугами (в примере их три). Для этого мы должны выяснить, сколько начальных символов таких у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя (это даст квадратичное время).
Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).
