http://agc011.contest.atcoder.jp/tasks/agc011_c

問題概要

N頂点M辺の単純無向グラフGが与えられる。Gの各頂点は1～Nまでの番号が付いている。Gを元にして以下のようなグラフG'を作ったとき、G'の連結成分の数を求めよ。

頂点数はN²
各頂点は1以上N以下の2整数の組(a, b)で番号付けされる
元のグラフGにおいてa-a'間, b-b'間にそれぞれ辺があるとき、G'の(a, b)-(a'-b')間に辺を張る

2 <= N <= 10⁵

0 <= M <= 2*10⁵

解法

G'の辺が張られる条件は、直観的には以下のように言い換えることができる（公式解説動画参照）。

元のグラフGの2頂点a, bにコマを置く
置いたコマを辺に沿って「同時に」動かす
この1回の操作の結果コマが頂点c, dに移れるとき、G'において(a, b) - (c, d)間に辺が張られる
この操作を繰り返して遷移できる頂点ペアはすべてG'において連結になる。

このように考えると、元のグラフでa-bが非連結であれば(a, *) - (b, *)に辺が張られることはありえないことがわかる。ゆえにまずはGを連結成分ごとに分解し、その単位で考えていくことにする。ここで分解した各連結成分を以下の3パターンに分類する。

孤立点
二部グラフ
それ以外

まず孤立点については辺がないので上で書いたような操作をどうやっても行うことができない。ゆえに元のグラフで頂点aが孤立点である場合G'においても (a, *) と (*, a) は孤立点になる（＝頂点ひとつで連結成分ひとつをなす）。

次に二部グラフについて。上の操作において選ぶ2頂点がいずれも二部グラフの上にあったとすると、同じ連結成分上にあってもたどり着けない組合せというものが出てくる。二部グラフを赤と青に塗り分けたとしたら、上の操作によるコマの移動は (赤, 赤) -> (青, 青) -> (赤, 赤) -> ...という遷移と(赤, 青) -> (青, 赤) -> (赤, 青) -> ,,,という2パターンになり決して交わらないので、これらはG'において2つの連結成分を作り出すということになる。

逆にどちらかのコマさえ非二部グラフの上に乗っているのならば、連結成分内のすべての頂点の組合せに遷移することができる。よってこの組み合わせにおいてG'に作り出される連結成分は1つだけである。

以上より解法はまず元のグラフを連結成分ごとに分解し、それぞれの連結成分を上の3パターンに分類したうえで、各組合せによってできる連結成分の数を足し合わせる、ということになる。気を付ける点として、最初の2コマを置く頂点が同じ連結成分内にある場合とそうでない場合で数え方が若干違う。もし(a, b)が同じ連結成分内に属していない場合、aが右に行ったりbが左に行ったりすることはないので、どちらの連結成分を左に置くかというところで2回同じカウントをする必要がある。

感想

うーん、５００００００００点！！！！

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0].to!int;
    auto M = s[1];
    auto edges = new int[][](N);
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        edges[s[0]-1] ~= s[1]-1;
        edges[s[1]-1] ~= s[0]-1;
    }
 
 
    int[][] groups;
    bool[] used = new bool[](N);
    int[] color = new int[](N);
    color.fill(-1);
 
    void dfs1(int n, int g) {
        if (used[n]) return;
        used[n] = true;
        groups[g] ~= n;
        foreach (m; edges[n]) if (used[n]) dfs1(m, g);
    }
 
    bool dfs2(int n, int c) {
        if (color[n] != -1) return color[n] == c;
        color[n] = c;
        foreach (m; edges[n]) {
            if (!dfs2(m, c^1)) return false;
        }
        return true;
    }
 
 
    int gn = 0;
    bool[] is_bi;
    foreach (i; 0..N) if (!used[i]) {groups ~= (new int[](0)); dfs1(i, gn++);}
    foreach (g; 0..gn) is_bi ~= dfs2(groups[g][0], g);
 
    long ans = 0;
 
    long G = groups.length;
    long one = groups.map!(g => g.length == 1).sum;
    long bi = is_bi.sum - one;
    long other = G - one - bi;
 
    ans += one * 2 * N - one * one;
    ans += bi * 2 + other;
    ans += bi * (bi - 1) * 2;
    ans += other * (other - 1);
    ans += other * bi * 2;
 
    ans.writeln;
}

nebukuro09の日記

AtCoder Grand Contest 011 C - Squared Graph

問題概要

解法

感想

コード (D言語)