[テストケース案] Matching on Bipartite Graph

[square1001]

Matching on Bipartite Graph について、Hopcroft-Karp 法を BFS で最短距離を求めてから DFS で増加路をまとめて探すわけでなく、これらを一気に 1 回の BFS で処理する実装をしている提出があります（https://snuke.hatenablog.com/entry/2019/05/07/013609 の「おまけ 2」で解説されている方法です）

しかし、このアルゴリズムには、ループが $\Theta\left(\frac{|V|}{\log |V|}\right)$ 回行われ、実行時間 $\Theta\left(\frac{|V|^2}{\log |V|}\right)$ かかるケースがあります。以下のコードで生成されるものです (L = R = 57344, M = 159744)。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int B = 12;
    vector<pair<int, int> > edges;
    for (int i = 0; i <= B; i++) {
        for (int j = 0; j < (1 << B); j++) {
            edges.push_back({(i << B) + j, (i << B) + j});
        }
    }
    for (int i = 0; i < B; i++) {
        for (int j = 0; j < (1 << B); j++) {
            edges.push_back({((i + 1) << B) + j, (i << B) + j});
            edges.push_back({((i + 1) << B) + (j ^ (1 << i)), (i << B) + j});
        }
    }
    for (int i = 0; i < (1 << B); i++) {
        edges.push_back({((B + 1) << B) + i, (B << B) + i});
    }
    for (int i = 0; i < (1 << B); i++) {
        edges.push_back({i, ((B + 1) << B) + i});
    }
    cout << ((B + 2) << B) << ' ' << ((B + 2) << B) << ' ' << edges.size() << endl;
    for (pair<int, int> e : edges) {
        cout << e.first << ' ' << e.second << endl;
    }
    return 0;
}

影響を受ける提出

上記のコードで生成されたテストケースでは、以下のコードでループ回数 4097, 4098 回となり、手元で実行したところ実行時間が 1000 ms 程度となりました。

• https://judge.yosupo.jp/submission/1548
• https://judge.yosupo.jp/submission/135842
• https://judge.yosupo.jp/submission/186050
• その他、数多くの実行時間上位の提出

また、上記のコードで生成されたテストケースでは影響を受けなかったものの、そのテストケースの辺を逆順にしたテストケースでは、以下のコードで同様の影響を受けました。

• https://judge.yosupo.jp/submission/154408 （現在最速の提出）
• https://judge.yosupo.jp/submission/162634
• その他、数多くの実行時間上位の提出

なお、辺の順番をシャッフルしたらループ回数が平均 45 回程度で終わるという問題点もあります（シャッフルしても平均的にループ回数が多くなるケースがあれば教えてほしいです）。

[maspypy]

提案されたものを特に考察せずにそのまま追加しました。 影響を受けるとされる 3 提出が影響を受けることを確認しました。

逆順にしたものを入れていなかったため、これも追加作業します。

[maspypy]

影響を受けるとされた 5 提出が影響を受けたことを確認したので、正しく入れられたと思います。 ありがとうございました。