Здравствуй, сообщество Codeforces!
Некоторое время назад, когда в университете зашла речь про систему непересекающихся множеств, у нас были некоторые люди с курса которые знали что это такое ( конечно, олимпиадники ), но на вопрос преподавателя "а где используется снм вне олимпиадных задач?" никто ответа так и не нашёл. Так вот, мне стало интересно, а действительно в каких НЕ олимпиадных задачах можно использовать снм, и на сколько её использование эффективно?
например, я однажды нашел реализацию СНМ в исходниках LLVM. https://github.com/llvm-mirror/llvm/search?q=IntEqClasses
можно ответить что-нибудь типа "используется для анализа потока управления в современных компиляторах" и привести ссылку на примеры.
Isn't this enough? I am pretty sure there are other fields these are just from top of my head.
Наверное, во многих задачах где приходится работать с классами эквивалентности.
Например, в VK Cup 2015 — Уайлд-кард раунд 2 было оговорено следующее "Мы постараемся подготовить тестовые данные так, чтобы факты списывания были достаточно очевидны человеку, а отношение списывания было транзитивным". Поэтому мне собирать результат с помощью СНМ было очень удобно.
Да, интересное применение
еще один пример http://habrahabr.ru/post/81279/
Оу, даже так! Спасибо!
Когда я проходил практику в лаборатории компьютерной графики, мы брали изображение, бинаризовали его, а потом искали на нем компоненты связности, используя СНМ. В итоге получилось очень даже неплохо и оказалось, что все это несложно распараллелить.
У меня тема дипломки связана с использованием суфмассива и СНМ в LZ77-кодировании со скользящим окном. Постараюсь сделать пост про это в конце мая.
К сожалению, программист я посредственный, поэтому реализация GZIP-совместимого упаковщика у меня получилась, скажем так, не очень производительная.
P.S. Английская статья в Википедии намного более понятная, чем русская.
Прочитайте на этом сайте http://e-maxx.ru/algo/dsu