## 10729 - Treequivalence

Moderator: Board moderators

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### 10729 - Treequivalence

Hello to Everybody!

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

Thank You!

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

### same label, be careful!!

Hey, a tree could consist of same labels.
I used OLE to test and found that. Be carful.

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 10729 - Treequivalence

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;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10729 - Treequivalence

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.
Check input and AC output for thousands of problems on uDebug!