AtCoder Grand Contest 011 C - Squared Graph

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;
}
Built with Hugo
テーマ StackJimmy によって設計されています。