AtCoder Beginner Contest 282D

ABC282D

atcoder.jp

DFSで連結成分ごとに計算する．

与えられたグラフに対して，すべての連結成分が2部グラフになっている必要がある．なぜなら，辺を追加して2部グラフなら，追加する前に2部グラフになっている必要があるため．

DFSにより，2部グラフか判定しながら，頂点に0,1で番号をつけていく．もし2部グラフになっていない連結成分があれば，そのことをフラグとして記録しておく．

以下，すべての連結成分が2部グラフになっている場合を考える．

[ 連結成分の内側 ]

(0の頂点の個数) * (1の頂点の個数)

を数えていく．

ただし，最初に与えらえたグラフの辺 M 本を最終的に引いておく．

[ 連結成分の外側 ]

連結成分同士は，辺を任意に追加してよい．

ただし，重複して数えてしまうので，2で割る．

(試験本番では，2で割る事に気づかずに解けなかった．)

コメント:

　数え上げるときは，

・重複なく，

・取りこぼしがない

様に数えるのが重要．

　また，計算が上手くいかないとき(WA, TLE, MLEなど)のときは，別の方法を試す．

・直接数える，

・補集合を使って数える，

・多めに数えて，あとで割る

など．複数の方法を持っておけば，上手くいかなくても別の方法で解ける場合がある．

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

using vll = vector<long long>;  using vvll = vector<vll>;

using pll = pair<ll,ll>;

int main() {

    ll n, m;

    cin >> n >> m;

    vvll to(n);

    vector<pll> ed(m);

    rep(i,m){

        ll a,b; cin >> a >> b;

        --a,--b;

        to[a].push_back(b);

        to[b].push_back(a);

        ed[i] = {a,b};

    }

    vll val(n, -1);

    bool flg = true;

    vll s(2);

    auto dfs = [&](auto f, ll cu, ll pa, ll x) -> void {

        if(val[cu] != -1){

            if(val[cu] != x) flg = false;

            return ;

        }

        val[cu] = x;

        s[x]++;

        fore(ne, to[cu]) if(ne != cu){

            f(f, ne, cu, x^1);

        }

    };

    ll ans = 0;

    ll tmp = 0;

    rep(i,n) if(val[i] == -1){

        s = vll(2);

        dfs(dfs, i, -1, 0);

        ans += s[0] * s[1];

        ll k = s[0] + s[1];

        tmp += k * (n-k);

    }

    assert(tmp % 2 == 0);

    ans += tmp /2;

    ans -= m;

    if(flg == false){

        cout << 0 << endl;

        return 0;

    }

    cout << ans << endl;

   

    return 0;

}