AtCoder Beginner Contest 157 参加記

D - Friend Suggestions 解説

問題文が長いですね。結論から言うとこの問題はグラフ問題に帰着できます。今回はUnionFind（以下UF）というデータ構造を使います。グラフやUFについての基本的な内容は他の記事を参照してください。

考察

まず友達関係に関するグラフを作ります。人を、番号のついた頂点とみなします。求めたいものは、各について、頂点と同じ連結成分に属する頂点のうち、頂点に隣接せず、かつ頂点とブロック関係にないものの個数です。図解すると以下のようになります。✔️のついた頂点のうち、ブロック関係にないものの個数を求めます。

実装

まずUFと、頂点の次数を管理するvectorを宣言します。また、vector>を用意します。set[i]を以下のように定義します。
set[i]:=頂点に隣接する頂点の集合

UnionFind tree(n);
vector<int> deg(n);//頂点の次数
vector<set<int>> st(n);
for(int i=0;i<m;i++){
        a[i]--;b[i]--;
        deg[a[i]]++;
        deg[b[i]]++;
        st[a[i]].insert(b[i]);
        st[b[i]].insert(a[i]);
        tree.unite(a[i],b[i]);
}

次に、頂点と同じ連結成分に属する頂点のうち、頂点と友達関係になく（に隣接せず）、かつブロック関係にあるものの個数を求めます。そのためのvectorを宣言し、で初期化します。UFのsame機能を使うことにより、二つの頂点が同じ連結成分に属するかどうかを判定できます。
u[i]:=頂点と同じ連結成分に属する頂点のうち、頂点に隣接せず、かつブロック関係にあるものの個数

vector<int> u(n,0);
for(int i=0;i<k;i++){
        c[i]--;d[i]--;
        if(tree.same(c[i],d[i])){
                if(!st[c[i]].count(d[i])) u[c[i]]++;
                if(!st[d[i]].count(c[i])) u[d[i]]++;
        }
}

最後に、各について、頂点と同じ連結成分に属する頂点の個数から、頂点に隣接する頂点の個数と、上記のu[i]と、（自身）を除けばよいです。

for(int i=0;i<n;i++){
        cout << tree.size(i)-deg[i]-u[i]-1 << ' ';
}

その他、精進記録など

3/1時点で以下のような感じです。



TopCoder 0
CodeForces 60
AtCoder 396
AOJ 17
yukicoder 0
Sum 473

もう少しでレート4桁です。遅くとも5月には水色になりたいです。