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;
}
|