poj 1635( 树的最小表示法判断同构 )
#include<stdio.h>#include<string>#include<string.h>#include<algorithm>#include<iostream>#include<vector>using namespace std;string dfs(char* ss,int s,int t){ int i,j=s,h=0; int cnt=0; vector<string> str; str.clear(); if( s>=t ) { string ans="01"; return ans; } for(i=s;i<=t;i++) { if( ss[i]=='0' ) cnt++; else cnt--; if( cnt==0 ) { str.push_back(dfs( ss,j+1,i-1 )); h++; j=i+1; } } sort(str.begin(),str.end()); string ans="0"; for(i=0;i<h;i++) ans+=str[i]; ans+="1"; return ans;}int main(){ int i,j,n; char str1[3010],str2[3010]; string ans1,ans2; scanf("%d",&n); while(n--) { scanf("%s",str1); scanf("%s",str2); ans1=dfs(str1,0,strlen(str1)-1); ans2=dfs(str2,0,strlen(str2)-1); if( ans1==ans2 ) printf("same\n"); else printf("different\n"); } return 0;}