POJ 1635 Subway tree systems(树同构)

题目链接：http://poj.org/problem?id=1635

题意：给出从根节点遍历树的两种方式，判断这两种方式是否是同一棵树。

思路：树的最小表示，其实就是对于根节点的若干子树DFS后重新排序。。。。

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;

struct node
{
    int L,R;
};

const int MAX=3005;
node a[MAX];
char s[MAX],A[MAX],B[MAX],temp[MAX];
int n,C;

int cmp(node a,node b)
{
    int len=min(a.R-a.L+1,b.R-b.L+1);
    int i;
    for(i=0;i<len;i++) if(s[a.L+i]!=s[b.L+i])
       return s[a.L+i]<s[b.L+i];
    return a.R-a.L<b.R-b.L;
}


void DFS(int L,int R,node *a)
{
    int pre=L,i,j,x=0,cnt=0;
    for(i=L;i<=R;i++)
    {
        if(s[i]=='0') x++;
        else x--;
        if(!x)
        {
            DFS(pre+1,i-1,&a[cnt]);
            a[cnt].L=pre;
            a[cnt].R=i;
            cnt++;
            pre=i+1;
        }
    }
    sort(a,a+cnt,cmp);
    x=0;
    for(i=0;i<cnt;i++) for(j=a[i].L;j<=a[i].R;j++) temp[x++]=s[j];
    x=0;
    for(i=L;i<=R;i++) s[i]=temp[x++];
}

int main()
{
    for(scanf("%d",&C);C--;)
    {
        scanf("%s",s); n=strlen(s); DFS(0,n-1,a); strcpy(A,s);
        scanf("%s",s); n=strlen(s); DFS(0,n-1,a); strcpy(B,s);
        if(strcmp(A,B)) puts("different");
        else puts("same");
    }
    return 0;
}