Tour [AtCoder Beginner Contest 204 C]

https://atcoder.jp/contests/abc204/tasks/abc204_c

前提知識

• BFS

解説

https://atcoder.jp/contests/abc204/submissions/23261589

この問題では実装方針から正しく計算量を見積もれるかがポイントとなる。
計算量見積もりをして、オーダーで上限を当てはめたときに10⁷くらいに抑える必要がある。
逆に、10⁷くらいまでは使ってもいいともいえる。

オーソドックスな問題

最後の都市の組として考える問題は珍しいので、もうちょっとオーソドックスな問題で考えてみよう。
普通に始点が固定だった場合は到達性問題になるので、その場合はBFSで解くことができる。
この問題が解けない場合は「BFS」や「到達可能性問題」あたりで調べて、理解してから次に進める。

BFSを普通にやってみると、O(N+M)となるので、これは十分に間に合う。
というか、計算量が余っている。
計算量が余っているので、もうちょっと無理ができる。

始点を全探索

よくよく考えるとスタート地点が全探索される必要があり、やっても間に合ってしまう。
スタート地点はN通りなので、O(N(N+M))が計算量となり、これは制約を見ると間に合う。
これが間に合うということが分かることが今回はキモとなる。

始点が変われば事象は独立になるので、それぞれの組み合わせを足せば答えになる。

int N, M;
vector<int> E[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
    }

    int ans = 0;
    rep(st, 0, N) {
        queue<int> que;
        set<int> vis;

        que.push(st);
        vis.insert(st);

        while (!que.empty()) {
            int cu = que.front(); que.pop();
            fore(to, E[cu]) if (!vis.count(to)) {
                que.push(to);
                vis.insert(to);
            }
        }

        ans += vis.size();
    }
    cout << ans << endl;
}