levonog's blog

Система непересекающихся множеств
By levonog, 10 years ago, In Russian

Здравствуй, сообщество Codeforces!

Некоторое время назад, когда в университете зашла речь про систему непересекающихся множеств, у нас были некоторые люди с курса которые знали что это такое ( конечно, олимпиадники ), но на вопрос преподавателя "а где используется снм вне олимпиадных задач?" никто ответа так и не нашёл. Так вот, мне стало интересно, а действительно в каких НЕ олимпиадных задачах можно использовать снм, и на сколько её использование эффективно?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it
  1. In type theory and functional programming. More precisely for finding degrees of freedom instantiating the rules.
  2. In multi-core computations. In order to effectively construct multi-core spanning forest one should use DSU.
  3. Contour trees are widely used in Multi-Resolution computations. To construct contour trees effectively one should use DSU.
  4. It also widely used in self-adjusting trees.(For example : adjusting-heaps).
  5. In order to maintain the condensation of the graph we also need to use DSU. Which is also widely used in software engineering.

Isn't this enough? I am pretty sure there are other fields these are just from top of my head.

→ Reply