AtCoder Grand Contest 011: C - Squared Graph

Dを優先してほぼ手を付けなかったが、解けていてもよい問題だった。

solution

連結成分への分解と奇閉路の検出をして、その数を元に計算。 $O(N + M)$ 。

元のグラフ上で互いに到達不能な頂点同士は、積グラフ上でも互いに到達不能な頂点群を生む。よって、元のグラフを連結成分に分解してその対ごとに考えてよい。次のように問題を読み替えられる: 連結グラフ $G_i$ ( $0 \le i \lt k$ )が与えられるので、各 $(i, j)$ について積グラフ $G_i \times G_j$ の頂点数を数え、その総和を答えよ。

連結グラフ $G, H$ をとる。 $G, H, G \times H$ の頂点数をそれぞれ $x, y, z$ とする。 $x = 1$ または $y = 1$ である場合は辺が $1$ 本も生まれないので $z = xy$ 。それ以外の場合では、 $G, H$ は共に連結なので $z \in \{ 1, 2 \}$ になる。 $x = y = 2$ の場合の積グラフが縦横に並ぶものと考えればそうなる。ここで $z = 1$ となるのは $G, H$ のどちらかが奇閉路を持つとき。つまり、それぞれのグラフを以下のように分類すれば十分:

$|V| = 1$
$|V| \ge 2$ かつ奇閉路がない
$|V| \ge 2$ かつ奇閉路がある

奇閉路の存在は二部グラフ性と同値なので、連結成分への分解の際にまとめてやるとよい。

implementation

#include <iostream>
#include <vector>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
int main() {
    // input
    int n, m; cin >> n >> m;
    vector<vector<int> > g(n);
    repeat (i,m) {
        int u, v; cin >> u >> v; -- u; -- v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // decompose
    int a_components = 0, a_nodes = 0; // connected graph: |V|  = 1
    int b_components = 0, b_nodes = 0; // connected graph: |V| >= 2 and no odd cyles
    int c_components = 0, c_nodes = 0; // connected graph: |V| >= 2 and odd cycles exist
    vector<char> used(n);
    repeat (root,n) if (not used[root]) {
        bool is_bipartite = true;
        int size = 0;
        queue<int> que;
        que.push(root);
        used[root] = 'A';
        while (not que.empty()) {
            int i = que.front(); que.pop();
            ++ size;
            for (int j : g[i]) {
                if (used[j]) {
                    if (used[i] == used[j]) is_bipartite = false;
                } else {
                    used[j] = (used[i] == 'A' ? 'B' : 'A');
                    que.push(j);
                }
            }
        }
        if (size == 1) {
            ++ a_components; a_nodes += size;
        } else if (is_bipartite) {
            ++ b_components; b_nodes += size;
        } else {
            ++ c_components; c_nodes += size;
        }
    }
    // calculate
    ll ans = 0;
    ans += a_nodes *(ll) a_nodes; // A A
    ans += 2 * a_nodes *(ll) b_nodes; // A B ; B A
    ans += 2 * a_nodes *(ll) c_nodes; // A C ; C A
    ans += b_components *(ll) b_components * 2; // B B
    ans += 2 * b_components *(ll) c_components; // B C ; C B
    ans += c_components *(ll) c_components; // C C
    // output
    cout << ans << endl;
    return 0;
}