POJ 1635 트리의 최소는 Hash를 나타냅니다.

나무의 동구 문제는 지금까지 나무의 최소 표시가 무엇인지 모르고 다른 사람의 코드를 참고했다. 자신만 참고할 수 있다.
Source Code
Problem:  1635
User:  sunyanfei
Memory: 748K
Time: 16MS
Language: G++
Result: Accepted

Source Code

/*

 * problem:poj 1635

 * Type:    

 */

#include<iostream>

#include<stdio.h>

#include<string>

#include<string.h>

#include<algorithm>

using namespace std;

const int maxn=3005;

struct node

{

	int depth,son;

}tree[maxn],tree2[maxn];

int cmp(const void* a,const void* b)

{

	node c=*(node*)a;

	node d=*(node*)b;

	if(c.depth==d.depth)return c.son-d.son;

	else return c.depth-d.depth;

}

int min_pre(char str[],node result[])

{

	int node_num=1,now=0;

	int father[maxn];

	father[0]=result[0].son=result[0].depth=0;

	for(int i=0;str[i];i++)

	{

		if(str[i]=='0')

		{

			father[node_num]=now;

			result[node_num].depth=result[father[node_num]].depth+1;

			result[node_num].son=0;

			now=node_num++;

		}

		else

		{

			result[father[now]].son+=result[now].son+1;

			now=father[now];

		}

	}

	qsort(result,node_num,sizeof(result[0]),cmp);

	return node_num;

}

int main()

{

	setbuf(stdout,NULL);

	char str[maxn];

	int T;

	cin>>T;

	while(T--)

	{

		scanf("%s",str);

		int num=min_pre(str,tree);

		scanf("%s",str);

		int num2=min_pre(str,tree2);

		if(num!=num2)

		{

			printf("different
");

			continue;

		}

		int i;

		

		for(i=0;i<num;i++)

		{

			if(tree[i].depth!=tree2[i].depth|| tree[i].son!=tree2[i].son)

			{

				printf("different
");

				break;

			}

		}

		if(i>=num)printf("same
");

	}

	return 0;

}