AtCoder Grand Contest 011 C

C - Squared Graph

概要

各頂点に $1 \sim N$ の番号が振られた $N$ 頂点 $M$ 辺の単純無向グラフが与えられる。

これを元に、 $(1, 1) \sim (N, N)$ まで番号の振られた $N^2$ 頂点からなるグラフを、以下の規則に基づいて作る。

元のグラフにおいて $a, a'$ 間にも $b, b'$ 間にも辺が存在する場合、またその場合にのみ $(a, b), (a', b')$ 間に辺を張る。

こうして作られたグラフの連結成分の数を求めよ。

制約

$1 \leq N \leq 10^5$
$0 \leq M \leq 2 \times 10^5$

解説

作られたグラフを具体的にイメージするのが非常に難しい。こういうときは多少手間でも手を動かすのが大事である。

実はサンプル 2 が非常に大きなヒントになっている。このサンプルで与えられるグラフの連結成分は以下の 3 パターンに分類できる。

2 色に塗り分けられるもの、つまり二部グラフ $(1, 2, 6)$
2 色で塗り分けられないもの $(3, 4, 5)$
1 頂点からなるもの、つまり孤立点 $(7)$

与えられたグラフにこれらの連結成分がそれぞれ $A, B, C$ 個あったとしよう。このとき、答えは $(A + B)^2 + A^2 + N^2 - (N - C)^2$ で与えられる。

なぜこれが成立するのかを説明するには私では力不足なので割愛。解説放送の石の説明がとてもわかり易いのでそちらを見るといいかと。

なお二部グラフ判定は多少面倒だが DFS で実装できる。

実装例

提出 #3195404 - AtCoder Grand Contest 011

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

vector<ll> path[100010];
int d[100010];
// 各頂点を0と1で塗り分ける

// 二部グラフならtrue
bool dfs(ll v, ll t) {
    if (d[v] >= 0) {
        return t == d[v];
    }

    d[v] = t;
    bool ret = true;
    for (ll sv : path[v]) {
        ret &= dfs(sv, 1 - t);
    }

    return ret;
}

int main() {
    ll N, M;
    cin >> N >> M;

    for (ll i = 0; i < M; ++i) {
        ll a, b;
        cin >> a >> b;
        --a;
        --b;
        path[a].push_back(b);
        path[b].push_back(a);
    }

    // 未探索なら-1
    fill(d, d + N, -1);

    ll even = 0, odd = 0, one = 0;
    // 二部グラフ、二部グラフでない連結成分と孤立点の数

    for (ll v = 0; v < N; ++v) {
        // 探索済みならパス
        if (d[v] >= 0) continue;

        // 孤立点判定
        if (path[v].empty()) {
            ++one;
            continue;
        }

        // 二部グラフ判定
        if (dfs(v, 0)) {
            ++even;
        } else {
            ++odd;
        }
    }

    cout << N * N - (N - one) * (N - one) + (odd + even) * (odd + even) + even * even << endl;
    return 0;
}