floppa322

Кажется нашёл проблему: алгоритм выше неправильно работает при наличии перекрёстных рёбер :(
Например, если было бы ребро из 10 в 5

Оффтоп

Вот, кстати, нашёл задачу, где dsu не асимптотически, но быстрее. чем dfs, ну и даже сам код лаконичнее и яснее

Конечно не очень хороший бенчмарк, но leetcode для dsu выдаёт в среднем 150 милисекунд, а для dfs 190 милисекунд, там для dfs, в частности, нужно ещё в список смежности превратить исходный массив, нужна мапа (медленная) для vertex To component, сет для used ну и сам код намного длинее выходит

В общем, dfs не очень работает с матрицей смежности и тем более списком ребёр (как в задаче выше), а только с списком смежности, поэтому если в задаче изначально граф дан не в нужном виде, то лучше использовать dsu, ну и также, чтобы рукам не поддерживать компоненты связности, так как это заложено в dsu. То есть если в ходе работы алгоритма нет чёткой структуры графа, или рёбра вообще появляются налету (находятся по каким-то признакам, а не даны заранее), то как раз через dsu удобно делать unite(from, to) этих рёбер

Вот ещё причину нашёл

В общем, всё оказалось довольно просто, если φ распределен неравномерно, то алгоритм следующий:

1. Найти ξ^(-1)(φ) (потому что значение исходной кси ξ^(φ) это как раз значение аргумента Fξ(x), чтобы по x находить множества φ (отрезки), которые ниже x
2. Результирующая Fξ(x) должна для каждого отрезка (которые ниже x) [a,b] просто вычислить вероятность множества этих [a, b] и суммировать их, используя Fφ(x): Fφ(b) - Fφ(a) (сами a и b это значения ξ^(-1)(φ))

Способ, описанный вопросе, это просто частный случай для равномерного распределения :)

Нашёл определение, оказывается это называется "Смешанное распределение", имеющее непрерывную и дискретную часть
если кому интересно

В общем, выяснилось, что это проблема XY
Но тем не менее, в академических целях, хотелось бы знать, является ли это strict aliasing violation или ещё чем-то

Нашёл некоторую информацию: на SO предполагают, что дело может быть в том что сам Mongo немного по-разному ведёт себя, когда к нему за единицу времени стучится 1 или несколько запросов
Та же проблема на SO