Редактирование: Алгоритм Хьюи

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
  
 
==Простое решение==
 
==Простое решение==
Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность составит <tex>O(V)</tex>.
+
Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность будет <tex>O(V)</tex>.
  
 
==Алгоритм решения==
 
==Алгоритм решения==
Строка 49: Строка 49:
 
   
 
   
 
  '''func''' dfs('''Node''' v)''':'''
 
  '''func''' dfs('''Node''' v)''':'''
     used[v] = ''true''
+
     used[v] = <b>true</b>
 
     '''for''' <tex>u \in</tex> v.children
 
     '''for''' <tex>u \in</tex> v.children
 
         '''if''' !used[u]
 
         '''if''' !used[u]
Строка 60: Строка 60:
 
  '''func''' hugh('''int''' n, '''int''' k, '''Node''' root)''':'''
 
  '''func''' hugh('''int''' n, '''int''' k, '''Node''' root)''':'''
 
     '''for''' <tex>v \in V</tex>
 
     '''for''' <tex>v \in V</tex>
         used[v] = ''false''
+
         used[v] = <b>false</b>
 
         sum[v] = 1
 
         sum[v] = 1
     '''for''' i = 1 '''to''' k
+
     '''for''' i = 1 to k
 
         last[i] = -1
 
         last[i] = -1
 
     dfs(root)
 
     dfs(root)

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: