程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 九度OJ 1035找出直系親屬

九度OJ 1035找出直系親屬

編輯：關於C++

題目描述：

如果A，B是C的父母親，則A，B是C的parent，C是A，B的child，如果A，B是C的（外）祖父，祖母，則A，B是C的grandparent，C是A，B的grandchild，如果A，B是C的（外）曾祖父，曾祖母，則A，B是C的great-grandparent，C是A，B的great-grandchild，之後再多一輩，則在關系上加一個great-。

輸入：

輸入包含多組測試用例,每組用例首先包含2個整數n（0<=n<=26）和m（0 當n和m為0時結束輸入。

輸出：

如果詢問的2個人是直系親屬，請按題目描述輸出2者的關系，如果沒有直系關系，請輸出-。
具體含義和輸出格式參見樣例.

樣例輸入：

3 2
ABC
CDE
EFG
FA
BE
0 0

這個題目第一眼看上去很像並查集，但是仔細分析可以發現，這個題目是利用已知條件構造森林然後對其中的關系進行查找。

題目的第一行的兩個輸入分別是所有的information的個數，第二個輸入是所有的quest的個數。

接下來的幾行是information，以ABC為例，B為A的parent，C為A的parent。根據這個關系，我們可以想到建立樹的方法：利用一維的數組存儲，然後數組中存放數組下標對應的子孫所在位置。那麼可以想到用stl中的map容器進行處理。

把森林（樹）構造完畢後，我們對所有的quest進行查詢。很自然就是順著child這個內容進行查找。下面函數的find就是實現這個功能。

PS:有一種很簡單的檢測程序對錯的測試辦法，記著二叉樹了沒？

#include
#include
#include
#include
using namespace std;
map temp;
map::iterator it;
struct node{
	char id;
	int child;
};
node rel[100];
int find(int x,int y)
{
	int count=0;
	while(x!=y&&x!=0)
	{
		count=count+1;
		x=rel[x].child;
	}
	if(x==0)
		return 0;
	else return count;
}
int main()
{
	int n,m,count,i,tra1,tra2,tra3;
	char a,b,c;
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		count=0;
		if(!temp.empty())
			temp.clear();
		for(i=1;i<100;i++)
			rel[i].child=0;
		for(i=1;i<=n;i++)
		{
			cin>>a>>b>>c;
			it=temp.find(a);
			if(a!='-'&&it==temp.end())
				temp.insert(pair(a,++count));
			it=temp.find(b);
			if(b!='-'&&it==temp.end())
				temp.insert(pair(b,++count));
			it=temp.find(c);
			if(c!='-'&&it==temp.end())
				temp.insert(pair(c,++count));
			if(a!='-')
				tra1=temp[a];
			if(b!='-'&&a!='-')
			{
				tra2=temp[b];
				rel[tra2].child=tra1;
			}
			if(c!='-'&&a!='-')
			{
				tra3=temp[c];
				rel[tra3].child=tra1;
			}
		}
		for(i=1;i<=m;i++)
		{
			cin>>a>>b;
			if(a=='-'||b=='-')
				cout<<"-"<0)
				{
					while(count1>=3)
					{
						cout<<"great-";
						count1=count1-1;
					}
					while(count1>=2)
					{
						cout<<"grand";
						count1=count1-1;
					}
					cout<<"parent"<0)
				{
					while(count2>=3)
					{
						cout<<"great-";
						count2=count2-1;
					}
					while(count2>=2)
					{
						cout<<"grand";
						count2=count2-1;
					}
					cout<<"child"<