連結グラフのランダム生成 (C++)

ランダムっぽく連結グラフをつくるやつ
|V| = 1e5, |E| = 1e7 で 4 sec くらい*1
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;



// http://chillbrains.hateblo.jp/entry/RandomSet
class RandomSet {
    struct Xor128 {
        unsigned x, y, z, w;
        Xor128(unsigned _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
        unsigned nextUInt() {
            unsigned t = (x ^ (x << 11));
            x = y; y = z; z = w;
            return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
        }
    } rnd;
    unordered_set<int> st;
    vector<int> v;
public:
    RandomSet(unsigned seed = 88675123) : rnd(seed) {}
    auto begin() { return st.begin(); }
    auto end() { return st.end(); }
    auto empty() { return st.empty(); }
    auto size() { return st.size(); }
    auto insert(int key) {
        auto ret = st.insert(key);
        if (ret.second == true)
            v.push_back(key);
        return ret;
    }
    auto random() {
        unsigned idx = rnd.nextUInt() % size();
        return v[idx];
    }
    auto pop_random() {
        unsigned idx = rnd.nextUInt() % size();
        auto key = v[idx];
        swap(v[idx], v.back());
        st.erase(key);
        v.pop_back();
        return key;
    }
};



// WTy : weight type
template<typename WTy> class RandomGraphGenerator {

    struct Xor128 {
        unsigned x, y, z, w;
        Xor128(unsigned _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
        unsigned nextUInt() {
            unsigned t = (x ^ (x << 11));
            x = y; y = z; z = w;
            return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
        }
    } rnd;

    int V, E;
    WTy W;

public:

    RandomGraphGenerator(int V, int E, WTy W = WTy(1), unsigned seed = 88675123) : V(V), E(E), W(W), rnd(seed) {}

    vector<tuple<int, int, WTy>> generate() {
        
        // e = (u, v) を (u << 32) + v にコンバートして管理
        unordered_set<ll> edges;
        edges.reserve(2 * E);

        // --- 全域木の生成 ---
        // T = {}, G = {0, 1, ..., |V| - 1}
        // G からランダムに始点 s を pop して T に追加
        // G が空になるまで:
        //     T からランダムに 1 点 u を選択
        //     G からランダムに 1 点 v を pop
        //     辺 e = (u, v) を張る
        //     v を T に追加
        RandomSet T(rnd.nextUInt()), G(rnd.nextUInt());

        for (int i = 0; i < V; i++)
            G.insert(i);
        T.insert(G.pop_random());
        for (int i = 0; i < V - 1; i++) {
            ll u = T.random();
            ll v = G.pop_random();
            edges.insert((u << 32) + v);
            T.insert((int)v);
        }

        // 辺が E 本になるまでランダムな 2 点に辺を張る
        int R = E - (int)edges.size();
        for (int i = 0; i < R; i++) {
            ll u, v;
            do {
                u = T.random();
                v = T.random();
                while (u == v) {
                    v = T.random();
                }
                if (u > v)
                    swap(u, v);
            } while (edges.find((u << 32) + v) != edges.end()); // 多重辺を避ける
            edges.insert((u << 32) + v);
        }

        // unordered_set の実装が環境依存なので
        // 同じ結果を得るためには sort する必要がある
        vector<ll> sorted_edges;
        sorted_edges.reserve(E);
        for (auto i : edges)
            sorted_edges.push_back(i);
        sort(sorted_edges.begin(), sorted_edges.end());

        vector<tuple<int, int, WTy>> weighted_edges;
        weighted_edges.reserve(E);

        for (const auto& e : sorted_edges)
            weighted_edges.emplace_back(int(e >> 32), int(e & 0xffffffff), WTy(rnd.nextUInt() % W + 1));

        return weighted_edges;
    }
};



// pll : (cost, dst)
ll MST(const vector<vector<pll>>& G) {
    const ll INF = 1LL << 60;
    int V = (int)G.size();
    vector<ll> mincost(V, INF);
    vector<ll> used(V, false);

    priority_queue<pll, vector<pll>, greater<pll>> pq;
    mincost[0] = 0;
    pq.push(pll(0, 0));
    ll MSTcost = 0;

    while (!pq.empty()) {
        pll p = pq.top(); pq.pop();
        int v = (int)p.second;
        if (used[v])
            continue;
        used[v] = true;
        MSTcost += mincost[v];
        for (int i = 0; i < G[v].size(); i++) {
            pll e = G[v][i];
            if (mincost[e.second] > e.first) {
                mincost[e.second] = e.first;
                pq.push(e);
            }
        }
    }

    return MSTcost;
}



int main() {

    int V = 100000;
    int E = 10000000;
    ll W = 10000;



    clock_t elapses = clock();

    RandomGraphGenerator<ll> rgg(V, E, W);
    auto edges = rgg.generate();

    elapses = clock() - elapses;
    cerr << "Generate random graph: " << double(elapses) / CLOCKS_PER_SEC << " sec." << endl;



    elapses = clock();

    vector<vector<pll>> G(V);
    for (const auto& e : edges) {
        ll u, v, w;
        tie(u, v, w) = e;
        G[u].push_back(pll(w, v));
        G[v].push_back(pll(w, u));
    }

    elapses = clock() - elapses;
    cerr << "Create adjacent list: " << double(elapses) / CLOCKS_PER_SEC << " sec." << endl;



    elapses = clock();

    ll MSTcost = MST(G);

    elapses = clock() - elapses;
    cerr << "Calculate MSTcost: " << double(elapses) / CLOCKS_PER_SEC << " sec." << endl;



    cout << "MSTcost: " << MSTcost << endl;
    return 0;
}