СНМ (наивные реализации) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:28:50Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:43, 1 сентября 2022

2022-09-01T04:43:17Z

185.79.217.61: оформление

2018-09-27T08:54:25Z

оформление

Roman: /* С помощью списка */

2015-04-28T18:05:08Z

‎С помощью списка

Shersh: /* Источники информации */

2014-06-13T12:22:00Z

‎Источники информации

Nastya: /* С помощью списка */

2014-06-13T12:05:36Z

‎С помощью списка

Nastya: /* С помощью списка */

2014-06-13T12:02:01Z

‎С помощью списка

Nastya: /* Источники информации */

2014-06-13T11:55:49Z

‎Источники информации

Nastya: /* С помощью списка */

2014-06-13T07:12:54Z

‎С помощью списка

Nastya: /* С помощью списка */

2014-06-13T07:07:55Z

‎С помощью списка

← Предыдущая		Версия 16:28, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.		'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.
	__TOC__		__TOC__

← Предыдущая		Версия 04:43, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.		'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.
	__TOC__		__TOC__

@@ Строка 30: / Строка 30: @@
 Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.
-<code>
   '''int''' s[n]
   '''func''' init():
       '''for''' i = 0 '''to''' n - 1
           s[i] = i               <font color=green> // сначала каждый элемент лежит в своем множестве </font>
-</code>
   '''int''' find(k):
       '''return''' s[k]
-</code>
   '''func''' union(x, y):
       '''if''' s[x] == s[y]
@@ Строка 49: / Строка 47: @@
               '''if''' s[i] == t
                   s[i] = s[x]
 === С помощью списка ===
@@ Строка 68: / Строка 65: @@
 Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.
   '''struct''' SetItem
       '''int''' data
@@ Строка 83: / Строка 79: @@
           s[i].tail = s[i]
           s[i].next = null
-</code>
   '''int''' find('''SetItem''' x):                        <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
       '''return''' x.head.data
-</code>
   '''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
       x = x.head
@@ Строка 99: / Строка 93: @@
           y.head = x
           y = y.next
-</code>
 [[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]

@@ Строка 71: / Строка 71: @@
   '''struct''' SetItem
       '''int''' data
-      '''int''' head
+      '''SetItem''' head
       '''SetItem''' next
       '''SetItem''' tail

@@ Строка 107: / Строка 107: @@
 == Источники информации ==
 * Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.
-* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]
 [[Категория: Дискретная математика и алгоритмы]]

@@ Строка 69: / Строка 69: @@
 <code>
-  '''srtruct''' nameOfStruct
+  '''struct''' SetItem
-      int head
+      '''int''' data
-      *nameOfStruct next
+     '''int''' head
-      int data
+      '''SetItem''' next
-  nameOFStruct s[n]
+  '''SetItem''' s[n]
   '''func''' init():
@@ Строка 83: / Строка 84: @@
 </code>
 <code>
-  '''int''' find(nameOfStruct x):                   <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
+  '''int''' find('''SetItem''' x):                        <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
       '''return''' x.head.data
 </code>
 <code>
-  '''func''' union(nameOfStruct x, nameOfStruct y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
+  '''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
       x = x.head
       y = y.head

@@ Строка 83: / Строка 83: @@
 </code>
 <code>
-  '''int''' find(nameOfStruct x):               <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
+  '''int''' find(nameOfStruct x):                   <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
       '''return''' x.head.data
 </code>
@@ Строка 92: / Строка 92: @@
       '''if''' x == y
           '''return'''
-      x.tail.next = y       <font color=green> // соединим списки </font>
+      x.tail.next = y                         <font color=green> // соединим списки </font>
-      x.tail = y.tail       <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font>
+      x.tail = y.tail                         <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font>
-      '''while''' y <tex> \neq </tex> null       <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font>
+      '''while''' y <tex> \neq </tex> null                         <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font>
           y.head = x
           y = y.next