ABC292 E - Transitivity のTLE解

概要

ABC292 E - Transitivity の解法で、辺を管理するデータ構造をsetにするとTLEした。

setをforでアクセスするとTLEすることはあったが、count() や insert() の 対数時間でTLEしたのは初めて。

解法とコード

「既存の辺(u,v)をすべてdequeに突っ込む。dequeから辺(u,v)を取り出し、辺(v,w)のうちまだ(u,w)に辺が無いなら、dequeに(u,w)を追加して答えを+1する。dequeが空になるまで繰り返す」という解き方をした。

辺を管理するデータをg[i][j] := iからjへ辺があるとする。

ここで辺を管理するデータ構造をset<pair<ll,ll>> edgeSetにするとTLEするので注意。

bitsetを使えばもっと早い。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll N, M; cin >> N >> M;
    vector G(N, vector<ll>());
    // set<pair<ll,ll>> edgeSet; // TLE
    // vector<bitset<2000>> g(N); // g[i][j] := iからjへ辺がある // AC
    vector g(N, vector(N, false)); // g[i][j] := iからjへ辺がある // AC
    deque<pair<ll,ll>> deq; // (u,v)
    for(ll i=0; i<M; i++) {
        ll u, v; cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        // edgeSet.insert({u,v});
        // g[u].set(v, 1);
        g[u][v] = true;
        deq.push_back({u,v});
    }

    ll ans = 0;
    while(!deq.empty()) {
        auto[u, v] = deq.front(); deq.pop_front();

        // vからwへの辺があるとき、uからwへの辺はあるか？
        for(ll w: G[v]) {
            if (u == w) continue;
            // if (!edgeSet.count({u,w})) {
            if (!g[u][w]) {
                // edgeSet.insert({u,w});
                // g[u].set(w, 1);
                g[u][w] = true;
                ans++;
                deq.push_back({u,w});
            }
        }
    }
    cout << ans << endl;
}


int main() {
    solve();
    return 0;
}