公式解説に具体的な実装方針などが書いていないため、一例を示します。あくまで一例であり、もっと簡潔な方法もあるかもしれません。

互いにフォロー・被フォローであることを FF と呼ぶことにすると、 \(x, y\) が FF で \(y, z\) が FF のとき \(x, z\) も FF となることが確かめられます。よって人をいくつかのグループに分け、グループ内は全て互いに FF であり、グループをまたぐと全て互いに FF でないようにできます。このグループを UnionFind などを用いて管理します。

また、 \(x\) が \(y\) をフォローしているとき、 \(x\) は \(y\) のグループの人を全員フォローしています。このことより、各グループに代表を定めて、各人についてその人がフォローしている代表のみを管理することにします。

これをもとに、以下の \(5\) つの集合を std::set などで管理します。また、現在の辺数 \(ans\) も持っておきます。

• \(FF[i]\) : \(i\) のグループの人の集合 (\(i\) が代表のときのみ)
• \(g[i]\) : \(i\) がフォローしている代表の集合
• \(h[i]\) : \(i\) のグループの人がフォローしている代表、つまり \(\bigcup_{j \in FF[i]} g[j]\) (\(i\) が代表のときのみ)
• \(rg[i]\) : \(g\) の逆辺
• \(rh[i]\) : \(h\) の逆辺

この状態から、 \(a\) が \(b\) をフォローするとどうなるかを考えます。 \(a, b\) のグループの代表をそれぞれ \(c, d\) とします。

まず、 \(c=d\) の場合、つまりこれは \(a, b\) が既に FF のとき、何もしなくて良いです。

次に \(d \in g[a]\) の場合、既に \(a\) が \(d\) のグループの人全てをフォローしているため、辺は増えません。

そうでないとき、 \(a\) は \(b\) をフォローしていません。このうち \(c \not\in h[d]\) のとき、グループの合併は起きません。単に \(g, h, rg, rh\) と \(ans\) に新たなフォローの分を加えるだけで良いです。

そうでないときに \(c\) のグループと \(d\) のグループは合併し、それぞれが FF になります。合併後の代表を \(c\) にすることにすると、合併するために必要な処理は順に以下のようになります。

1. \(c\) のグループの人へのフォローと \(d\) のグループの人へのフォローの分を、一度 \(ans\) から引く
2. \(d\) のグループから \(c\) へのフォロー、 \(c\) のグループから \(d\) へのフォローを削除する
3. \(d\) へのフォローを \(c\) へのフォローに変える
4. \(h[d]\) を \(h[c]\) へ移し、 \(rh[w]\) に \(d\) が入っている \(w\) について \(rh[w]\) から \(d\) を消し \(c\) を入れる
5. \(ans\) に \(\lvert FF[c] \rvert \times \lvert FF[d] \rvert\) を足す
6. \(FF[d]\) を \(FF[c]\) に移し、 UnionFind をマージする
7. \(ans\) に \(c\) へのフォローの分を足す

なお、同じグループ内のフォロー関係が \(g, h, rh\) に入っていても、後で参照するときに気を付ければ良いため、 2. では \(rg\) のみ変更すれば良いです。 1. と 7. のためにグループの人をフォローしている人の数を \(O(1)\) で取得したいため、 \(rg\) は変更する必要があることに注意してください。

また、この合併の後にさらに合併をする必要があるグループは、 \(x \in h[d]\) かつ \(c \in h[x]\) なる \(x\) か、 \(y \in rh[d]\) かつ \(c \in rh[y]\) なる \(y\) のいずれかが代表です。

以上の操作は全て \(FF[d], g[d], h[d], rg[d], rh[d]\) のサイズのみに依存した計算量で行えます。また最終的なサイズもそれぞれ \(M\) で抑えられるため、合計でも \(5M\) 以下になります。よって、これら \(5\) つのサイズの和が大きい方に小さい方をマージすることを考えれば、いわゆるデータ構造をマージする一般的なテクニックにより、計算量は \(O(N \log N \log M)\) で抑えられます。

詳しくは実装を参照してください。なお実装例ではこれを用いて \(FF\) を陽に管理していません。

実装例