Problem 1217 : Family Tree
問題概要
John Robert Frank Andrew Nancy David
のような家系図が与えられる。
このとき、
X is a child of Y. X is the parent of Y. X is a sibling of Y. X is a descendant of Y. X is an ancestor of Y.
の問いが与えられるので、それぞれについてTrueかFlaseで答えよ。
解法
家系図は、人の名前とその人の親を覚えるようなデータ構造に入力すればよい。
ソースコード
int n,m; vector<string> nm; int p[1000]; map<string,int> id; bool ck(int a,int b) { for(;a>=0;a=p[a])if(a==b)return 1; return 0; } int main() { while(cin>>n>>m,n) { nm.clear(); id.clear(); cin.ignore(); string str; int sp=0,psp=0,pa=-1; rep(i,n) { getline(cin,str); for(sp=0;str[sp]==' ';sp++); nm.pb(str.substr(sp)); id[nm[i]]=i; if(psp>sp) { rep(j,psp-sp)pa=p[pa]; p[i]=pa; } else if(psp==sp)p[i]=pa; else if(psp<sp)p[i]=i-1,pa=i,sp++; psp=sp; } rep(i,m) { string n1,n2,t; cin>>n1>>str>>str>>t>>str>>n2; n2.erase(n2.end()-1); int a=id[n1],b=id[n2]; bool ans=0; if(t=="child")ans=p[a]==b; else if(t=="parent")ans=p[b]==a; else if(t=="sibling")ans=p[a]==p[b]; else if(t=="ancestor")ans=ck(b,a); else ans=ck(a,b); cout<<(ans?"True":"False")<<endl; } cout<<endl; } return 0; }