辺を構築していく問題を解くためのテクニックについて

はじめに

辺を構築していく問題を解くテクニックについて書きます。全然一般的には使えませんが、とりあえず以下の $2$ 問が似たような感じで解けます。

C - 3 Steps
F - Blackout

どちらの問題も距離を適切に定義してやると簡単に解けます（というか二問目は辺を構築する発想に至るまでの方が難しいかもという感じなんですが...）。

一問目

C - 3 Steps

概要：頂点数 $n$ 、辺数 $m$ の連結な無向グラフが与えられます。ある頂点 $u$ から辺をちょうど $3$ 本たどって到達できる異なる頂点 $v$ が存在し、$u, v$ 間に辺が存在しないとき、$u, v$ 間に辺を追加できます。このとき、追加できる辺の数は最大何本かを求めてください。

まずある頂点 $A$ を固定して、その頂点から各頂点までの距離を考えると、以下のようになります。

さて、異なる二頂点であって、その距離が $3$ であるものの間には辺が張れるのでした。そこで、頂点 $A$ と 頂点 $D$ に辺を張ることができそうです。

このとき、上図のように頂点 $D$ の距離は $1$ に書き換えても構いません。さらに、頂点 $E, F$ の距離はそれぞれ $2,\ 3$ と書き換えることができます。

すると今度は頂点 $F$ の頂点 $A$ からの距離が $3$ になるので、この二頂点間にも辺を張れそうです。

これを繰り返すと、結局すべての頂点は $A$ からの距離が $1$ か $2$ にできることがわかります。さらに、距離 $1$ と書かれた頂点と、距離 $2$ と書かれた頂点に辺を張ることもできます。なぜなら、例えば次のグラフで頂点 $I$ から頂点 $A$ への距離は $2$ で、頂点 $B$ から頂点 $A$ への距離は $1$ なので、頂点 $I$ と頂点 $B$ の距離を $3$ にすることができるからです。逆に $1$ と書かれた頂点と $2$ と書かれた頂点の間には辺は張れません。

これで、すべての頂点を交互に塗り分けられる場合の答えはわかりました。この性質を持つグラフを二部グラフと呼ぶので、グラフが二部グラフのときは解けました。

では、グラフが二部グラフではないときはどうすればよいでしょう。まずグラフが二部グラフではないという条件は、少なくとも一つの奇閉路をもつという条件に言い換えることができます。

例えば以下のようなグラフでは、頂点 $D$ をどちらの色でも塗れてしまいそうです。

このときは、頂点 $D$ は距離 $1$ でもあるし、距離 $2$ でもあると考えるのが自然なので、どちらの色も塗ってしまいます。するとその他の頂点も両方の色を塗れることに気づくはずです。

（頂点 $A$ は便宜上 $2$ と書いています）

このような場合は、すべての頂点がすべての色をもつと考えられるので、任意の頂点間に辺が張れます。

よって、奇閉路があるかどうかを判定し、あるならばすべての頂点間に辺を張り、ないならば、距離 $1$ と書いた頂点の個数と距離 $2$ と書いた頂点の個数に辺を貼れば良いです。

以下の実装では二部グラフかどうかを判定し、二部グラフならその片方の色の頂点数を返すライブラリを貼り付けています。

#include <cstdio>
#include <vector>
#include <functional>

using namespace std;

int BipartiteGraph(const vector<vector<int>> &g) {
        int n = g.size();
        vector<int> color(n, -1);
        int white_cnt = 0;
        function<bool (int, int, int)> dfs = [&](int u, int prev, int c) {
                color[u] = c;
                if (c == 1) white_cnt ++;
                for (auto v : g[u]) if (v != prev) {
                        if (color[v] == -1) {
                                if (!dfs(v, u, 1 - c)) return false;
                        } else if (color[v] != 1 - c) {
                                return false;
                        }
                }
                return true;
        };
        if (!dfs(0, -1, 0)) return -1;
        return white_cnt;
}

int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d %d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        int cnt = BipartiteGraph(g);
        if (cnt == -1) printf("%lld\n", (long long) n * (n - 1) / 2 - m);
        else printf("%lld\n", (long long) cnt * (n - cnt) - m);
        return 0;
}

二問目

F - Blackout

概要：$n$ × $n$ のマスがあって、そのうち $m$ 個が黒く塗られていて、その他は白です。マス $(x, y)$ とマス $(y, z)$ がともに黒ならば、マス $(z, x)$ を黒く塗ることができます。この操作をできる限り繰り返すと、最終的に黒いマスは何個できるかを求めてください。

注意：以下の解説は厳密な証明ではなく、発想法をわかりやすく書いているので、細かいところは気にせず読んでください。

まずマス $(x, y)$ が黒い、という条件を頂点 $x$ から頂点 $y$ に向かう辺が存在する、という条件に読み替えます。すると、上の操作は、頂点 $x$ から頂点 $y$ に辺が存在し、頂点 $y$ から頂点 $z$ に辺が存在するとき、頂点 $z$ から頂点 $x$ に辺を張る、という操作に読み替えることができます。

さて、一問目と同様に、ある頂点からの距離を見ていきます。とりあえず次のようなグラフを考えます。

操作を一度加えると、次のようなグラフができます。

さて、ここで $3$ つ目の頂点の距離はどのように変わるでしょうか？実際には距離と呼ぶのはおかしいのですが、矢印の順方向に進む距離を正の距離とし、逆方向に進む距離を負の距離と定義することにします。すると、もともと距離が $2$ だった頂点を次のように $-1$ に書き換えても良さそうです。

さらにこの $-1$ からの距離を考えることで、右のほうの頂点の距離も次のように書き換えることができます。

さて、また距離 $2$ の頂点があるので、これを $-1$ に書き換えます。これを繰り返すと、すべての頂点は $3$ 色で塗ることができます。

自明に張れる辺をすべて張ると次のようになります。

さて、これらの辺は、必ず次のいずれかを満たす頂点間に張られています。

$0$ → $1$
$1$ → $-1$
$-1$ → $0$

辺は正の距離が $1$ 増加するように張っているので当然ですね。

そして少し考えると、上のいずれかのペアである任意の頂点間には辺を張ることができます。例えば、一番右の頂点から、左から $2$ 番目の頂点に辺を張ることを考えます。

まず、以下のような $-1$ → $0$ の辺が張れます。

よって次の $0$ → $1$ の辺が張れます。

このようにして、上の順番を満たす任意の頂点間に辺を張ることができます。

それでは、この順番がどうしても作れない場合（一問目では二部グラフではない場合に相当する）はどうすればよいでしょうか。この場合は、上と同様に、各頂点に複数の距離を定義してやることにすればよいです。グラフに次のような、$3$ 色できれいに塗れない構造があったとします。

まず $0$ を基準に書くと次のようになります。

自明な辺を張ると次のように双方向に結ぶ辺ができます。

すると次のような自己辺ができます（グラフが汚すぎる）。

なんだかんだで次のようにすべて塗れます（矢印は気にしないでください）。

これをグラフの他の部分にも繰り返すことですべての頂点がすべての色を持つと考えることができ、したがって任意の頂点間に辺が張れます。自己辺も張ることができます。このようにして、一問目と同じような性質が見えました。

あとは細かい部分を詰めればよいです。以上でこの問題も解けました。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <cassert>
using namespace std;

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<int>> g(n), rg(n);
        UnionFind uf(n + 1);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d %d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                rg[b].push_back(a);
                uf.unite(a, b);
        }
        vector<int> color(n, -1);
        long long x, y, z, edge;
        function<bool (int, int)> dfs = [&](int u, int c) {
                if (color[u] == -1) {
                        color[u] = c;
                        if (c == 0) x ++;
                        else if (c == 1) y ++;
                        else if (c == 2) z ++;
                        else assert(false);
                } else if (color[u] != c) {
                        return true;
                } else {
                        return false;
                }
                for (auto v : g[u]) {
                        edge ++;
                        if (dfs(v, (c + 1) % 3)) return true;
                } 
                for (auto v : rg[u]) {
                        edge ++;
                        if (dfs(v, (c + 2) % 3)) return true;
                }
                return false;
        };
        long long ans = 0;
        for (int i = 0; i < n; i ++) if (!uf.same(i, n)) {
                long long sz = uf.get(i);
                uf.unite(i, n);
                x = 0, y = 0, z = 0, edge = 0;
                bool all = dfs(i, 0);
                if (all) {
                        ans += sz * sz;
                } else if (y == 0 || z == 0) {
                        ans += edge / 2;
                } else {
                        ans += x * y + y * z + z * x;
                }
        }
        printf("%lld\n", ans);
        return 0;
}

まとめ

どちらの問題も、辺の張り方のルールから、どの距離がどの距離と等しいとみなせるのかを考え、グラフの構造からきれいに色（距離）を塗っていけるかを判定し、きれいに塗れる場合は、特定の色の頂点間のみに辺が張れて、きれいに塗れない場合はすべての頂点にすべての色を塗ってしまって、任意の頂点間に辺を張ることができる、という性質を使って解くことができました。

以上です。