2022-12-23

AtCoder ABC 282 D - Make Bipartite 2 (緑色, 400 点)

一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！

その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の単純な無向グラフが与えられます。頂点番号を $1, 2, \dots, N$ とします。

このグラフにおいて、以下の条件を満たす頂点の組 $(u, v)$ ( $1 \le u \lt v \le N$ ) の個数を答えてください。

頂点 $u, v$ を結ぶ辺が存在しない
頂点 $u, v$ を結ぶ辺を追加したグラフは二部グラフである

制約

$2 \le N \le 2 \times 10^{5}$
$0 \le M \le 2 \times 10^{5}$

考えたこと

二部グラフとは、下図のように、

白色の頂点同士が隣接しない
黒色の頂点同士が隣接しない

という条件を満たすように、各頂点を白黒に塗り分けられるようなグラフ。

二部グラフ判定はたとえば、けんちょん本などに書いた。他にも次の記事などにも書いた。

qiita.com

平たく言えば、二部グラフの判定方法は次のような感じになる。

グラフの連結成分のうち、まだ考えていない連結成分について、1 つの頂点を選んで「白色」に塗る (黒色でもよい)
その頂点とつながる頂点に対しては、次々と連鎖的に色が決まっていく
その決まった色が整合性を取れない場合は二部グラフではない
以上の作業を、連結成分がなくなるまで繰り返す

連結成分ごとに考える

冒頭に書いた通り、「グラフの問題を連結成分ごとに考える問題へと帰着する」という方針で考える。

まず、連結成分の中に二部グラフでないグラフがあった時点で、グラフ全体も二部グラフではない。以降は、グラフが二部グラフであるものとして考えることにする。

さて、この問題で追加する辺を次の 2 つの場合に分けて考える。

同じ連結成分同士の 2 頂点を結ぶ辺
異なる連結成分間の 2 頂点を結ぶ辺

1. 同じ連結成分同士の 2 頂点を結ぶ辺

同じ連結成分内部の辺については次のように考えられる。二部グラフ判定したときの

白色の頂点の個数を $a$ 個
黒色の頂点の個数を $b$ 個
すでにある辺の本数を $m$ 本

としたときに、 $ab - m$ 本の頂点組には辺を追加できる。なお、後述するように、実際には「連結成分ごとに $m$ を求める」という作業は必要ない。

ここで気になるのは、連結成分の色の塗り方によっては、 $a, b$ の値が変わってしまうのではないかということだ。

しかし実はその心配はない。二部グラフ判定においては「1 つの頂点の色を決めると残りの頂点の色も自動的に決まる」ということを利用する。

よって、「白色： $b$ 個」「黒色 $a$ 個」というように $a, b$ が入れ替わることはあっても、値が変わることはないのだ。

2. 異なる連結成分間の 2 頂点を結ぶ辺

実は、二部グラフと二部グラフの間をどう結んでも、二部グラフのままなのだ。

たとえ同じ色同士を結んでしまったとしても、片方の連結成分の色を反転させればよい。

まとめ

以上の考察をまとめよう。結べる頂点組の個数を数えるよりも、結べない頂点組の個数を数える方が楽そうなので、ここではそうする (どっちでも正解できる)。

結んではいけない辺は「同じ連結成分内の、同じ色の頂点同士」ということがわかる。

具体的には、同じ連結成分内の白色頂点の個数を $a$ 、黒色頂点の個数を $b$ としたとき、結んではいけない辺の本数は

$\displaystyle \frac{a(a-1)}{2} + \frac{b(b-1)}{2}$

と表せる。これを各連結成分について合算すればよい。

全体として、計算量は $O(N + M)$ となる。

コード

ここでは BFS で実装する。

Python3

import queue

# N  * (N - 1) // 2
def com(N):
    return N * (N - 1) // 2

# 色
WHITE, BLACK = 0, 1

# 入力
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
G = [[] for _ in range(N)]
for e in edges:
    u, v = e[0]-1, e[1]-1
    G[u].append(v)
    G[v].append(u)

# 各変数
num_ng_edges = 0
is_bipartite = True
color = [-1] * N

# 各連結成分を走査する
for s in range(N):
    if color[s] != -1: continue

    # 白色頂点、黒色頂点の個数
    white_num, black_num = 0, 0

    # 頂点 s を始点とする BFS
    que = queue.Queue()
    que.put(s)
    color[s] = WHITE
    while not que.empty():
        v = que.get()

        # 頂点の個数をカウント
        if color[v] == WHITE: white_num += 1
        else: black_num += 1

        # 頂点 v の隣接頂点について
        for v2 in G[v]:
            if color[v2] != -1:
                # すでに色が塗られているとき
                if color[v2] == color[v]:
                    # 隣接頂点が同色はダメ
                    is_bipartite = False
            else:
                # 新しい頂点を処理
                color[v2] = 1 - color[v]
                que.put(v2)

    # ng 辺の本数
    num_ng_edges += com(white_num) + com(black_num)

# 答え
print(com(N) - M - num_ng_edges if is_bipartite else 0)

C++

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;  // グラフのデータ構造

// 色
const int WHITE = 0;
const int BLACK = 1;

int main() {
    // 入力
    long long N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    long long num_ng_edges = 0;
    bool is_bipartite = true;  // 二部グラフかどうか
    vector<int> color(N, -1);  // 各頂点の色

    for (int s = 0; s < N; ++s) {
        if (color[s] != -1) continue;

        // 白色頂点、黒色頂点の個数
        long long white_num = 0, black_num = 0;

        // 頂点 s を始点とする BFS
        queue<int> que;
        que.push(s);
        color[s] = WHITE;  // 頂点 s を白色に塗る
        while (!que.empty()) {
            int v = que.front();
            que.pop();

            // 頂点の個数をカウント
            if (color[v] == WHITE) 
                ++white_num;
            else
                ++black_num;

            // 頂点 v の隣接頂点について
            for (auto v2 : G[v]) {
                if (color[v2] != -1) {
                    // すでに色が塗られているとき
                    if (color[v2] == color[v]) {
                        // 隣接頂点が同色はダメ
                        is_bipartite = false;
                    }
                } else {
                    // 新しい頂点を処理
                    color[v2] = 1 - color[v];
                    que.push(v2);
                }
            }
        }

        // ng 辺の本数
        num_ng_edges += white_num * (white_num - 1) / 2
                        + black_num * (black_num - 1) / 2;
    }

    // 答え
    if (is_bipartite)
        cout << N * (N - 1) / 2 - M - num_ng_edges << endl;
    else
        cout << 0 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます