【abc157-D】①BFS練習

※注意
この記事は、主に自分用に執筆したものです。ので、各所にお気持ちが伝わりづらい(伝わらない)言い回しやコードが散見されるかもしれませんがご了承ください。

#まえがき
[AtCoder Beginner Contest 157](https://atcoder.jp/contests/abc157)(後解き)。
A~Cは大丈夫。Dはこの間勉強したBFSで解けるなと思ったので、まずこれで実装した。BFS自体はいい感じで割とスムーズに書けたんだけど、微妙に実行が間に合わなくて色々足掻いた跡をここに綴る。
解説PDFとかを見ていると、この問題は**Union-Find**とかいうデータ構造を用いることでも解ける(むしろそっちが第一解法？)らしい。そっちもあとで勉強しようかな。あと普通にDFSでもいいよね。
※abc157-D(Friend Suggestions).Difficulty: 1151


#本編
これは問題からグラフを処理してください感がビンビン出てるしそうしよう。なんとなくグラフに慣れてきた感があって嬉しい。
まずは例によって本能的に突き進んで書き切った初回コードを貼る。

##初回コード
```abc157/d.cpp
#include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;

void bfs(const Graph& friends, const Graph& block, int* unit, int n, int i) {
    if(unit[i]==0) {
        bool seen[n];
        for(int j=0; j<n; j++) seen[j]=false;
        seen[i] = true;
        queue<int> todo;
        todo.push(i);
        int count = 1;

        while(!todo.empty()) {
            int v = todo.front();
            todo.pop();
            for(auto next_v : friends[v]) {
                if(seen[next_v]) continue;
                seen[next_v] = true;
                todo.push(next_v);
                count++;
            }
        }
        for(int j=0; j<n; j++) {
            if(seen[j]) {
                int fri = friends[j].size();
                int blo = 0;
                for(int k=0; k<block[j].size(); k++) {
                    if(seen[block[j][k]]) blo++;
                }
                unit[j] = count - (fri+blo+1);
            }
        }
    }
}

int main() {
    int n,m,k;
    cin>>n>>m>>k;
    Graph friends(n);
    Graph block(n);
    for(int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        friends[a-1].push_back(b-1);
        friends[b-1].push_back(a-1);
    }
    for(int i=0; i<k; i++) {
        int c,d;
        cin>>c>>d;
        block[c-1].push_back(d-1);
        block[d-1].push_back(c-1);
    }

    int unit[n];
    for(int i=0; i<n; i++) unit[i]=0;

    for(int i=0; i<n; i++) {
        bfs(friends, block, unit, n, i);
    }

    for(int i=0; i<n-1; i++) cout<<unit[i]<<' ';
    cout<<unit[n-1]<<endl;

    return 0;
}
```

概要としては、BFSによって各頂点がいくつの頂点からなる連結成分に属するかを調べて、その中のフレンドとブロックと自分自身を除いた数を出力する、という感じ。

これはそれなりに身を入れて読む価値があるくらい、BFSのアルゴリズムがきちんと機能してるしいい方針。ただ結果としては、テストケースの5/30にTLEで弾かれた。んーメインアルゴリズムBFSの計算量はそんなに大きくなってないはずなんだけど。
というわけで計算量を減らすためにコードを精査する旅に出た。ら未熟者なのでなかなか帰ってこれなかった。でもまあ無事帰還したのでその成果を。

##ACコード
```abc157/d2.cpp
#include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;

void bfs(const Graph& friends, vector<int>& numbering, int* unit, bool* seen, int number, int n, int i) {
    seen[i] = true;
    unit[i] = number;
    queue<int> todo;
    todo.push(i);
    int count = 1;

    while(!todo.empty()) {
        int v = todo.front();
        todo.pop();
        for(int next_v : friends[v]) {
            if(seen[next_v]) continue;
            seen[next_v] = true;
            unit[next_v] = number;
            todo.push(next_v);
            count++;
        }
    }
    numbering.push_back(count);
}

int main() {
    int n,m,k;
    cin>>n>>m>>k;
    Graph friends(n);
    int fri[n];
    for(int i=0; i<n; i++) fri[i]=0;

    for(int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        friends[a-1].push_back(b-1);
        friends[b-1].push_back(a-1);
        fri[a-1]++;
        fri[b-1]++;
    }

    int unit[n];
    bool seen[n];
    for(int i=0; i<n; i++) {
        unit[i] = -1;
        seen[i] = false;
    }

    int number = 0;
    vector<int> numbering;
    for(int i=0; i<n; i++) {
        if(unit[i]==-1) {
            bfs(friends,numbering,unit,seen,number,n,i);
            number++;
        }
    }

    int ans[n];
    for(int i=0; i<n; i++) {
        ans[i] = numbering[unit[i]] - fri[i] -1;
    }

    for(int i=0; i<k; i++) {
        int c,d;
        cin>>c>>d;
        if(unit[c-1]==unit[d-1]) {
            ans[c-1]--;
            ans[d-1]--;
        }
    }

    for(int i=0; i<n-1; i++) cout<<ans[i]<<' ';
    cout<<ans[n-1]<<endl;

    return 0;
}
```

これならかなり余裕を持って計算が終わる。
色々細かく直したんだけど、従来のコードでの戦犯はおそらくbfs関数内のforループ。ここがテストケースによっては時間かさんでたかな。blockはグラフにせず、入力を受け取った瞬間にその情報を反映させるようにしたことと、seen配列は全体で1つだけ作ればいいことに気づけたのが勝因。numberingとかは別にやらなくてもよかったかもね。

一応教訓としてまとめておくと、

- コード中の各ブロックで最悪の場合を想定して、計算量が溢れないようにしましょう。
- bfs部門の計算量は $O(N+M)$ です。ちゃんと実感しましょう。(実感した)
- 配列とかvectorを関数へ渡すプレイに自信がないからこういうことになるんですよ。もっと慣れましょう。

って感じかな。あと最後にすごくしょーもないことに気づいたから書いとくんだけど、これグラフの名前を`friend` にするとバグります。なんか関数に対して**フレンド宣言**みたいなことができるらしく、そこでブッキングしたぽい。とりま深入りはしないけどそういうことで。
↑こういう風に、既に言語によって使用されていて変数名等で再定義できないフレーズのことを、正式には**予約済みキーワード**と呼ぶらしいです。ご指摘感謝します。

#あとがき
新しくアルゴリズムを学んだわけじゃないし、いよいよ自分にしか需要がないみたいな記事になった。勉強進めてったらだんだんそうなるのかなあ。執筆時間も相当短くなってたし。
とりあえず練習積むのが大事感しかないし頑張りましょう。次はコンテスト内に解き終わるくらいの早さでACしたい。てかこの問題結構Difficulty高いんだな。この辺倒せるようになれば水色見えてくるのかな。

あとがきみたいなあとがきを書いたのも初めてだ。ちょっとエモい。では。