3 Steps [CODE FESTIVAL 2017 予選B C]

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c

前提知識

• 二部グラフ判定

解法

http://code-festival-2017-qualb.contest.atcoder.jp/submissions/1671264

細かな証明は公式解説にあるが、解法の結論から言うと、
　

• グラフが二部グラフでないなら、N(N-1)/2-Mが答え
• グラフが二部グラフなら、BW-Mが答え

　
なので、とりあえず二部グラフ判定をする。

二部グラフ判定
dfsをして貪欲に黒(=1)と白(=2)に塗っていけばいい。
塗っていく過程で同じ色が隣り合ってしまうなら、それは二部グラフではない。
　
判定ができたら、上記の式に従って答えを求めるだけ。

typedef long long ll;
int N, M;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
int col[101010];
int ok = 1;
void dfs(int cu) {
    fore(to, E[cu]) {
        if (col[cu] == col[to]) {
            ok = 0;
            return;
        }

        if (!col[to]) {
            col[to] = 3 - col[cu];
            dfs(to);
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    col[0] = 1;
    dfs(0);

    if (ok) {
        int B = 0, W = 0;
        rep(i, 0, N) {
            if (col[i] == 1) B++;
            else W++;
        }

        ll ans = 1LL * B * W - M;
        cout << ans << endl;
    } else {
        ll ans = 1LL * N * (N - 1) / 2 - M;
        cout << ans << endl;
    }
}