問題
http://community.topcoder.com/stat?c=problem_statement&pm=13759&rd=16461
N個のノード、N-1のエッジからなる木がある。
どのノードとエッジが接続しているかわからないが、各ノード間の距離が
偶数ならE,奇数ならOであるという情報が与えられている。
このとき、与えられた情報で木が再現できるならそのエッジの例を一つ出力する。
そうでない場合はー１を返す。
解き方
まずは木でつながっていることから、一つの木（例えばノード０）からのエッジが
すべてEなら再現できない。
上記を満たす場合、一つのノード０を基準にして、
・ノード０からの距離が偶数同士のノード間エッジはE
・偶数と奇数であればO
・奇数同士であればE
であるか判定し、存在する場合は一つのエッジO（例えばノード０～ノード３）
を固定して、そこからエッジを伸ばしていけば有効なエッジの集合となる。
コード
class OddEvenTree {
public: vector<int> getTree(vector<string> x) {
int n=x.size();
int d[n];
vector<int> invalid(1,-1);
int flag=1;
FORE(i,0,n)if(x[0][i]=='O')flag=0;
if(flag)return invalid;
FORE(i,0,n)d[i]=(x[0][i]=='O');
FORE(i,0,n)FORE(j,0,n){
int cur=(x[i][j]=='O');
if(cur!=(d[i]^d[j]))return invalid;
}
int r0=0,r1;
FORE(i,0,n)if(x[0][i]=='O')r1=i;
vector<int> ans;
ans.push_back(r0),ans.push_back(r1);
FORE(i,1,n)if(i!=r1){
if(d[i]){
ans.push_back(r0),ans.push_back(i);
}else{
ans.push_back(i),ans.push_back(r1);
}
}
return ans;
}
};
public: vector<int> getTree(vector<string> x) {
int n=x.size();
int d[n];
vector<int> invalid(1,-1);
int flag=1;
FORE(i,0,n)if(x[0][i]=='O')flag=0;
if(flag)return invalid;
FORE(i,0,n)d[i]=(x[0][i]=='O');
FORE(i,0,n)FORE(j,0,n){
int cur=(x[i][j]=='O');
if(cur!=(d[i]^d[j]))return invalid;
}
int r0=0,r1;
FORE(i,0,n)if(x[0][i]=='O')r1=i;
vector<int> ans;
ans.push_back(r0),ans.push_back(r1);
FORE(i,1,n)if(i!=r1){
if(d[i]){
ans.push_back(r0),ans.push_back(i);
}else{
ans.push_back(i),ans.push_back(r1);
}
}
return ans;
}
};