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;
}