DSU

[key-moon]

C#的な命名をしたい箇所:

• Same→IsSame
• Leader→GetLeader
• Size→GetSize

[key-moon]

DSUの経路縮約は3種類くらいあって、どれを採用するか問題 https://twitter.com/satanic0258/status/1102947824348495873

Path Compression: いつもの 再帰使うので愚直だと遅いかも 愚直

public int Leader(int a) => ParentOrSize[a] < 0 ? a : ParentOrSize[a] = Leader(ParentOrSize[a]);

非再帰

private int[] buffer = new int[1024];
public int Leader(int a)
{
    int ptr = 0;
    while (0 <= ParentOrSize[a])
    {
        buffer[ptr++] = a;
        a = ParentOrSize[a];
    }
    ptr--;
    while (0 <= ptr)
    {
        ParentOrSize[buffer[ptr]] = a;
        ptr--;
    }
    return a;
}

Path Splitting: 全てを2個上につなげる

public int Leader(int a)
{
    if (ParentOrSize[a] < 0) return a;
    while (0 <= ParentOrSize[ParentOrSize[a]])
    {
        (a, ParentOrSize[a]) = (ParentOrSize[a], ParentOrSize[ParentOrSize[a]]);
    }
    return ParentOrSize[a];
}

Path Halving: Splittingの一部をサボるがテンポラリ変数を使わない

public int Leader(int a)
{
    while (true)
    {
        if (ParentOrSize[a] < 0) return a;
        if (ParentOrSize[ParentOrSize[a]] < 0) return ParentOrSize[a];
        a = (ParentOrSize[a] = ParentOrSize[ParentOrSize[a]]);
    }
}

AtCoder/Library Checkerに出して比較してみましたが、よく分かりませんでした（悲しい）。 チューニングは結局後々するので、とりあえず今はSplittingにしておきます。

[key-moon]

実装しました。 https://github.com/key-moon/ac-library-cs/blob/2b8ac05c75e9d4665d90cd345dd494d55bef147e/AtCoderLibrary/DSU.cs Verify: https://atcoder.jp/contests/practice2/submissions/16569240