Page 1 of 1

### 10729 - Treequivalence

Posted: Thu Oct 07, 2004 8:41 pm
Hello to Everybody!

Can anybody help me, say any hints, how to solve this problem?

Thank You!

### same label, be careful!!

Posted: Tue Mar 27, 2007 6:00 am
Hey, a tree could consist of same labels.
I used OLE to test and found that. Be carful.

### Re: 10729 - Treequivalence

Posted: Sat May 31, 2014 4:59 pm

Code: Select all

``````#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const

using namespace std;

int main()
{
int i,j,k,m,n,t;
cin>>t;
getchar();
while(t--)
{
vector<int>v[205],v2[205];
string s1,s2;
getline(cin,s1);
getline(cin,s2);
map<char,int>mp;
int cnt=0;
stack<char>s;
char ch;
for(i=0,j=s1.size();i<j;i++)
{
if(s1[i]==',')
{
continue;
}
if(s1[i]!=')')
{
if(s1[i]!='(')
{
if(!mp[s1[i]])
mp[s1[i]]=++cnt;
}
s.push(s1[i]);
}
else
{
queue<char>q;
while(s.top()!='(')
{
ch=s.top();
s.pop();
q.push(ch);
}
s.pop();
ch=s.top();
k=mp[ch];
while(!q.empty())
{
ch=q.front();
q.pop();
m=mp[ch];
v[k].push_back(m);
v[m].push_back(k);
}
}
}
for(i=0,j=s2.size();i<j;i++)
{
if(s2[i]==',')
{
continue;
}
if(s2[i]!=')')
{
if(s2[i]!='(')
{
if(!mp[s2[i]])
mp[s2[i]]=++cnt;
}
s.push(s2[i]);
}
else
{
queue<char>q;
while(s.top()!='(')
{
ch=s.top();
s.pop();
q.push(ch);
}
s.pop();
ch=s.top();
k=mp[ch];
while(!q.empty())
{
ch=q.front();
q.pop();
m=mp[ch];
v2[k].push_back(m);
v2[m].push_back(k);
}
}
}
bool ok=true;
for(i=1;i<=cnt&&ok;i++)
{
sort(v[i].begin(),v[i].end());
sort(v2[i].begin(),v2[i].end());
j=v[i].size();
k=v2[i].size();
if(j!=k)
ok=false;
j=0;
while(j<k&&ok)
{
if(v[i][j]!=v2[i][j])
ok=false;
j++;
}
}
if(ok)
cout<<"same\n";
else
cout<<"different\n";
}
return 0;
}
``````

### Re: 10729 - Treequivalence

Posted: Fri Jun 13, 2014 11:00 pm
Input:

Code: Select all

``````100
T(T(Y(T),M(R)),P,J,C(H))
R(M(T(T(P,J,C(H)),Y(T))))
T(B)
B(T)
U(P(K),F)
P(U(F),K)
I(S(B(Q(W,A),N(M),H)),H)
S(B(Q(W,A),N(M),H),I(H))
F(L(V),G(Q))
L(F(G(Q)),V)
J(E(M))
M(E(J))
U(A(K,B,Z,I))
U(A(K,B,Z,I))
A(W(S,T),X)
A(W(S,T),X)
S(Y(Y(O),U(N(S,E,R(D)))))
D(R(N(U(Y(Y(O),S)),S,E)))
U
U
Y(F(A(Q(X,W),L(U)),V))
X(Q(A(L(U),F(V,Y)),W))
C(L(Z),V)
V(C(L(Z)))
G(B(D(L(Y(Z))),J,X,T,V))
B(D(L(Y(Z))),J,X,G,T,V)
O
O
Y(Y(D(P(M(C),V,P),L)))
Y(D(P(M(C),V,P),L),Y)
Z(Y(U,Y,B),R)
U(Y(Y,Z(R),B))
K(B(Q(L),V,K,F),Y(A))
B(K(Y(A)),Q(L),V,K,F)
E(Q(P(U(J),F),W),P)
P(E(Q(P(U(J),F),W)))
C(G(Y(R(I))))
I(R(Y(G(C))))
I(K(F(P)))
F(K(I),P)
X
X
U(M(Y(J,V),O,Y))
V(Y(M(U,O,Y),J))
P(C(C(H)),O(E))
P(C(C(H)),O(E))
X(T(L(Q)),Q(T(C)))
C(T(Q(X(T(L(Q))))))
J(E(T,X(V),I),N(Z,W(Y)))
Y(W(N(J(E(T,X(V),I)),Z)))
D
D
J(R,N(I(G)))
I(N(J(R)),G)
C(N(Y(E(E)),E,I))
C(N(Y(E(E)),E,I))
Y(X(H(C,G(W)),M,G(R)))
R(G(X(H(C,G(W)),M,Y)))
M(Q(T))
T(Q(M))
W(E(T))
W(E(T))
O(C)
C(O)
K(L,D)
K(L,D)
T(Q(V(J(R,E))))
V(J(R,E),Q(T))
Q(F,K(V(G)),T,U,K)
U(Q(F,K(V(G)),T,K))
P(Z)
P(Z)
A(V)
A(V)
C(I,T(U))
U(T(C(I)))
F(V(V(U(K,C),N(K,T)),C))
K(U(V(V(F,C),N(K,T)),C))
T(M(R(P(C,L,S),D)))
T(M(R(P(C,L,S),D)))
O(E)
O(E)
J(P(O(B,G)))
G(O(P(J),B))
F(J(I(X),A),Y,Z(I))
X(I(J(F(Y,Z(I)),A)))
Q(Q)
Q(Q)
W(O(V(S(E(V(L(S(U(Q)))))))))
Q(U(S(L(V(E(S(V(O(W)))))))))
C(F)
F(C)
J(W(R,C))
C(W(R,J))
Q(U,J,Z)
U(Q(J,Z))
B(T(C(P(U),W),D(A),Y))
P(C(W,T(D(A),Y,B)),U)
O(W,R(A))
O(W,R(A))
Y(J(A(C,O(Y)),K))
Y(J(A(C,O(Y)),K))
S(S(F))
S(S,F)
B(W(O,W))
O(W(W,B))
M(E(A,Y(I(F(T,K))),O))
I(Y(E(A,M,O)),F(T,K))
S(E(D))
E(S,D)
P(U(D,D(F(A(E))),I))
E(A(F(D(U(D,P,I)))))
X(P(U))
U(P(X))
K(D(I,D,K))
D(D(I,K,K))
F(C(H,B(C),N))
B(C(H,N,F),C)
R(P(L(Y(A(T),K),D)))
T(A(Y(L(P(R),D),K)))
A(M(G(Z),I))
G(M(A,I),Z)
O(T(B))
O(T(B))
A(Y(V),D)
Y(A(D),V)
M(V(W(F(C)),W(N)))
M(V(W(F(C)),W(N)))
K(T(V,J))
V(T(K,J))
F(D(W,V))
D(W,V,F)
A
A
O(K(C(X(J(C)),E(S(V)))),Y)
C(J(X(C(E(S(V)),K(O(Y))))))
Z(M(D(F(B,D),K),M(T)),E)
F(D(M(M(T),Z(E)),K),B,D)
K(S(W(X,J)),U(T,B))
J(W(S(K(U(T,B))),X))
R
R
S(F(Y(S,M,B,R)))
M(Y(F(S),S,B,R))
F(D(W(K(X(D),B)),L))
D(W(K(X(D),B)),L,F)
C(B(X(U(V))))
B(C,X(U(V)))
K
K
X(T(P(Q)))
P(T(X),Q)
U
U
W(S(Z(M),I(S,C)))
S(I(S(W,Z(M)),C))
W(T,R)
T(W(R))
Z(E,J)
Z(E,J)
B(C(Q(B(C(D),W(O)))))
W(B(C(D),Q(C(B))),O)
J(X(N(H,N),B))
J(X(N(H,N),B))
K(M(D,W(J(M(Y)),R),B,D))
D(M(W(J(M(Y)),R),K,B,D))
I(E)
E(I)
Q(M(C(R)))
M(Q,C(R))
W(O)
O(W)
K(I(O),F(T(L),J,O))
I(K(F(T(L),J,O)),O)
M(Q(K(G)),T)
M(Q(K(G)),T)
G(S(K(N(C(O))),D))
C(N(K(S(G,D))),O)
S(H(Q(I(A(T(J)),B,V))))
S(H(Q(I(A(T(J)),B,V))))
U(Q(P,H),T)
P(Q(H,U(T)))
V(J(W(Y(W)),E,R),H(Y))
J(V(H(Y)),W(Y(W)),E,R)
P(X(J),Q,N(H))
J(X(P(Q,N(H))))
J(N(Q(G(O),R(O),U)),Q,Y)
O(R(Q(G(O),N(J(Q,Y)),U)))
U(H(R))
H(R,U)
V(S)
V(S)
R(B(R,U))
B(R,R,U)
R(G(V(Z(W(Y(J))))))
R(G(V(Z(W(Y(J))))))
X(X,Q,G(R),X(X))
X(X,Q,G(R),X(X))
H
H
``````
AC output:

Code: Select all

``````same
same
same
same
same
same
same
same
different
same
different
same
different
same
same
different
same
same
same
same
same
different
same
same
same
same
same
same
different
same
same
same
same
same
different
same
same
same
different
same
same
same
different
same
same
same
different
same
same
same
same
same
same
different
same
different
same
different
different
different
different
same
same
same
different
same
same
same
different
same
same
different
same
same
same
same
same
different
same
same
different
same
different
same
same
same
same
same
different
same
same
same
same
different
same
same
same
same
same
same
``````
Note that order must be preserved.