ABC199 D 解答
D - RGB Coloring 2 (1804)
問題文
N 頂点 M 辺の単純無向グラフがあります。頂点には 1 からN までの、辺には 1 からM までの番号がついています。
辺 i は頂点 Ai と頂点 Bi を結んでいます。このグラフの各頂点を赤、緑、青の 3 色のいずれかで塗る方法であって、以下の条件を満たすものの数を求めてください。
辺で直接結ばれている 2 頂点は必ず異なる色で塗られている
なお、使われない色があっても構いません。
制約
1 ≤ N ≤ 20
0 ≤ M ≤ N*(N−1)/ 2
1 ≤ Ai ≤ N
1 ≤ Bi ≤ N
与えられるグラフは単純 (多重辺や自己ループを含まない)
考察
グラフの色ぬりを考える問題です。こんな言い方をすると怒られるかもしれませんが、本問題の理論の部分は結構簡単です。ただし、それを実装してみましょう、といわれると途端にわからなくなります。私もとても苦戦しました。ですので、本記事ではその実装で苦戦した点などの説明に重点を置いて書いていきます。
まずは、理論の部分です。どんな感じでやると答えが求められそうかを説明します。
まず、注目すべきは頂点数の少なさです。なんと、最大でも20頂点しかありません。これを見て、なんとなく全部探索できそうだな、指数時間で計算できるな、みたいなことを考えることができます。
ただし、本問題で用いる色はRGBの三色です。本当に全頂点に全ての色のパターンを当てはめますと
3^20 = 3.4*10^9
です。これだとちょっと間に合わなさそうですね。困りました。
ここで、問題の条件に注目します。
「辺で直接結ばれている 2 頂点は必ず異なる色で塗られている」
この条件を考慮して色を考えます。まず、１頂点目は他に何も塗られていないので、3通りです。でも、２頂点目は１頂点目で塗られた色は塗ることができませんので、２通りしかありません。３頂点目は１と２のいずれか、もしくはその両方に繋がっています（今は連結グラフを考えます）。ですので、１か２通りです。別の言い方をするなら多くても２通りです。これは残りの頂点の全てに言えますので、条件を考慮したパターン数は
3*2^19 = 1.5*10^6
です。だいぶ可愛らしい数になってきました。これくらいなら全部試しても大丈夫そうです。
以上より本問題は
隣り合う頂点と異なる色となるグラフを全探索する
することで、答えを求めるられます。こう聞くと簡単そうですね、全部の色を試せば良いのですから。
でもここからが、とっても大変です。心して聞いてください。
今回はDFSによりグラフを構築していきます。
頂点を通ったら色を塗っていき、帰るときにその色を消していきます。そんな感じで、全ての頂点に色をつけることができたら、そのグラフはOKということになり答えに＋１します。
ここで大切なのが、
１）末端まで行った時の処理
２）探索順序
です。順を追って説明します。
まずは１）末端まで行った時の処理です。
通常のDFSでは末端まで行くと来た道を戻っていきます。当然です。そういうアルゴリズムです。ただし、これだと今回は困ります。先にも述べましたが、探索の終点は
隣り合う頂点と異なる色となるグラフ
です。塗られていない頂点があってはいけないのです。でも、DFSでは戻るときに頂点の色を消してしまいます（DFSだからというわけではないですが）。これだと塗られていない頂点が出てくることがあります。
これを解決するために
先にDFSで探索をしておき探索順をメモする
という処理を行います。AtCoder様の解説で言いますと、
適当な頂点 (ここでは頂点 1 とする) から同じ頂点を 2 度通らないDFS (深さ優先探索) をし、頂点を訪れた順に入れた配列 s を作る
という部分です。これにより、次の図のように全部の頂点に色をつけることが可能となります。
もちろん色をつけるのはその頂点と隣り合う頂点に使用されていない色に限られます。
最後の頂点 7 まで行く、もしくはどの色でも塗れないとなりましたら、ようやくその色を消しながら戻ります。
このときの色の付け方、消し方の順番に関して
２）探索順序
ということで説明を続けます。といいましても、１）に比べればシンプルな話です。DFSを行う際に、例えばですが
Rの色を連結する頂点に渡す。
Bの色を、、Gの色を、、
とやるのと、
頂点をRで塗って次の頂点に移る
Bで塗って、、Gで塗って
みたいにすると実装によっては探索順序が異なります。ここで大事なのは
１）で事前に求めた探索順序に従って探索をする
ということです。さすがに順序をあえて変えて実装するということはないと思いますが、、ですので、色を塗れるかどうかの判定に連結を管理するグラフを使って、次の頂点への遷移には事前に調べた探索順を用います。
探索に関してはこんな感じでしょうか。ただ注意点がもう一つだけあります。ここま、触れずに来ましたが、本問題では
グラフが連結とは限らない
のです。つまり一回の探索で全ての頂点を巡ることができないかもしれません。ただこれはそんなに大変な問題でもなかったりします。グラフが連結してないということは連結成分ごとに独立に考えられます。例えば、グラフ１が３通り、グラフ２が12通りの塗り方があったとしましょう。グラフ１の各通りに対してグラフ２が対応しますので、総数は掛け算の３６通りになります。入力例４の答えがなんか大きい原因はこれです。全部独立してると、全部掛け算になってしまいます。
あとはバグに気をつけて実装をしていくだけです。とはいっても、なかなか複雑ですので、コメントにて補足をして行きます。
実装
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
vector<vector<int>> g(20);
vector<int> prm;
vector<int> used(20,-1);
//探索順序をもとめる
//探索順序をprmにいれる
void dfs1(int s)
{
//一度訪れた頂点をメモ
used[s] = 1;
//通った頂点を順番に入れて行く
prm.emplace_back(s);
for(auto e:g[s])
{
//通った頂点には行かない
if(used[e]!=-1)continue;
dfs1(e);
}
}
//頂点の色を管理
vector<int> color(20,-1);
//塗り方を全探索
//lは今まで塗った頂点数
int dfs2(int l)
{
int res = 0;
//もし、全部塗れてたら+1をかえす
if(l == prm.size()) return 1;
//次の頂点
//prmには頂点が順番で入ってる
int s = prm[l];
//使用可能な色
vector<int> c(3);
for(auto e: g[s])
{
if(color[e]==-1) continue;
//隣り合う頂点で使われてたら+1
++c[color[e]];
}
rep(i,3)
{
//0のものだけ使える
if(c[i]!=0)continue;
//色をつけて次の頂点へ
//グローバルのカラーに書き込む
color[s] = i;
res += dfs2(l+1);
//戻るときには色を消す
color[s] = -1;
}
return res;
}
int main()
{
int n,m;
cin >> n >> m;
rep(i,m)
{
int a,b;
cin>> a>>b;
--a,--b;
g[a].emplace_back(b);
g[b].emplace_back(a);
}
ll ans = 1;
rep(i,n)
{
//通った頂点は1となっている。
//連結しているので飛ばす。
if(used[i] == 1) continue;
//配列をからにしておく
prm.clear();
//頂点iから順番をprmに追加していく
dfs1(i);
//色情報をリセット、全部の色を消す。
rep(j,n) color[j] = -1;
//頂点数0から探索開始
ans *= dfs2(0);
}
cout << ans << endl;
return 0;
}あとがき
少し補足です。本記事では例として木で考えてますが木とは限りません。
でも全く同じ考えで大丈夫です。
この問題は難しかったです。特に「色を消さずにここに行きたい」という点を理解するまでにかなりの時間がかかりました。
はじめはDFSにて、ある頂点に連結している頂点に関してその頂点を塗ることができる色を渡して探索を進めていました。やはりこれだと、末端まで行った際に塗られていない頂点ができてしまいます。本当に困りました。言ってしまえば、塗り方の全探索なのですが、かなり工夫と根気のいる全探索だったと思います。実装もバグをたくさん発生させてとても疲れました。このDFSが解ければなかなかのものだと思いますので、お時間があるときに挑戦してみてはいかがでしょうか。
本問題の類題と言えるか怪しいかもしれませんが、ABC198Eも色に関して書いて、消してを行うDFSの問題でした。いくらかそちらの方が優しいと思いますので、そちらに挑戦してからの方が良いかもしれませんね。
また、別解もたくさんありました。赤の色をbit全探索して、二分グラフで判定など、みなさん賢い方法を考えてすごいです。私はこの方法だけで精一杯でした。
この記事が気に入ったらサポートをしてみませんか？