SRM658 Div1 Easy OddEvenTree
問題
文字の $N \times N$ 行列 $x$ が与えられる。 これは頂点数 $N$ のグラフについて、 $x[i][j]$ が $\mathrm{E}$ なら $i$ と $j$ の距離が偶数、$\mathrm{O}$ なら奇数であることを表す。 ただし距離とは頂点間にある辺の数である。 この行列と矛盾しない木は存在するか判定し、存在するなら構築せよ。
方針
まず、自明な条件を確認しておく(fcheck関数)。
木は $2$ 部グラフなので隣り合わないように赤と青に塗れる。 行列の $0$ 行目を見て、 $x[0][i]$ が $\mathrm E$ なら赤、$\mathrm O$ なら青に塗ることにする。 一色しかない場合はそもそも連結でないので存在しない。 また、ある頂点への距離の偶奇は色が同じか異なるかだけで決まるので、赤の点の行は $x[0]$ と、青の点の行はその遇奇裏返しと一致しないといけない。
次にグラフを構築していく。 適当に $1$ つ赤の点を選び、それに全ての青の点を接続する。さらに適当に $1$ つ青の頂点を選び、それに全て赤の頂点を接続する。 するとこのグラフは偶奇の条件を満たす。
問題を解く上では不要だが、ある辺を切って、片方の部分木を同じ色の頂点に付け替えても行列は変化しないので、 偶奇の条件を満たす任意の木は、このようにして作った木に変形することができる(逆も然り)。
実装
vi const FALSE {-1};
class OddEvenTree {
public:
vector <int> getTree( vector <string> x ) {
int n = x.size();
if(!fcheck(x)) return FALSE;
set<string> m;
rep(i,n) m.insert(x[i]);
if(m.size() != 2) return FALSE;
if(!isinv(*m.begin(),*m.rbegin())) return FALSE;
vector<int> ve, vo;
rep(i,n){
if(x[0]==x[i]){
if(x[0][i] != 'E') return FALSE;
ve.pb(i);
} else {
if(x[0][i] != 'O') return FALSE;
vo.pb(i);
}
}
if(ve.size()==0) return FALSE;
dump(vo);
dump(ve);
vector<int> res;
rep(i,vo.size()){
res.pb(0);
res.pb(vo[i]);
}
rep(i,ve.size()){
if(ve[i]==0) continue;
res.pb(vo[0]);
res.pb(ve[i]);
}
return res;
}
bool fcheck(vector<string> const & x){
int n = x.size();
rep(i,n)rep(j,n) if(x[i][j] != x[j][i]) return false;
return true;
}
bool isinv(string const & s, string const & t){
int n = s.size();
rep(i,n) if(s[i]==t[i]) return false;
return true;
}
};