解題區/解題區 - UVa

UVa 10729 - Treequivalence

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個平面圖的樹，請問是否同構，每一個節點相鄰的邊將會按照逆時針的順序給定。

Sample Input

1
2
3
4
5
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

Sample Output

1
2
different
same

Solution

這一題與 UVa 12489 - Combating cancer 有點不同，這一題限制在平面圖，因此邊的紀錄是有順序性的。而題目不僅要求結構相同，同時在節點上面的 label 也要相同。

但是只要固定一個當作根，成為一個有根樹，那麼在最小表示法中，除了根的分支可以旋轉外，其餘的節點的分支都不能旋轉。因此固定其中一棵樹的根節點，接著窮舉另外一棵樹哪個節點作為根節點，分別找到最小表示法進行比對即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
// special !!!!!!!! normal planar representation
class Tree {
    public:
    vector<int> g[10005];
    char label[10005];
    int n;
    map<vector<int>, int> tmpR;
    int dfsMinExp(int u, int p) {
        vector<int>	branch;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(v == p)	continue;
            branch.push_back(dfsMinExp(v, u));
        }
        sort(branch.begin(), branch.end());
    
        int a = 63689, b = 378551;
        int ret = 0;
        branch.push_back(label[u]);
        for(int i = 0; i < branch.size(); i++)
            ret = ret * a + branch[i], a *= b;
        return ret;
    }
    vector<int> getTreeMinExp() { // simple (no plane)
        if(n == 1)	return vector<int>(1, (int)label[1]);
        int deg[10005] = {}, u, v;
        int topo[10005] = {}, idx = 0;
        queue<int> Q;
        for(int i = 1; i <= n; i++) {
            deg[i] = g[i].size();
            if(deg[i] == 1)	Q.push(i);
        }
        while(!Q.empty()) {
            u = Q.front(), Q.pop();
            topo[idx++] = u;
            for(int i = 0; i < g[u].size(); i++) {
                v = g[u][i];
                if(--deg[v] == 1)
                    Q.push(v);
            }
        }
        vector<int> ret;
        ret.push_back(dfsMinExp(topo[idx-1], -1));
        ret.push_back(dfsMinExp(topo[idx-2], -1));
        return ret;
    }
    
    int dfsCheck(Tree& tree, int u, int p) {
        vector<int> branch;
        if (p < 0) { // root
            for (int i = 0; i < tree.g[u].size(); i++) {
                int v = tree.g[u][i];
                branch.push_back(dfsCheck(tree, v, u));
            }
            
            int idx = 0, bn = branch.size();
            for (int s = 1; s < bn; s++) { // find cycle minExp
                for (int i = idx, j = s, k = 0; k < bn; k++) {
                    if (branch[i] != branch[j]) {
                        if (branch[j] < branch[i])	idx = s;
                        break;
                    }
                    if (++i >= bn)	i = 0;
                    if (++j >= bn)	j = 0;
                }
            }
            rotate(branch.begin(), branch.begin() + idx, branch.end());
        } else {
            int idx;
            for (idx = 0; tree.g[u][idx] != p; idx++);
            
            while (true) {
                idx++;
                if (idx >= tree.g[u].size())
                    idx = 0;
                int v = tree.g[u][idx];
                if (v == p)	break;
                branch.push_back(dfsCheck(tree, v, u));
            }
        }
        branch.push_back(-tree.label[u]);
        int &ret = tmpR[branch];
        if (ret == 0)	ret = tmpR.size();
        return ret;
    }
    int equal(Tree &other) { // normal planar representation
        if (n != other.n)	return 0;
        tmpR.clear();
        int b = dfsCheck(other, 1, -1);
        for (int i = 1; i <= n; i++) {
            int a = dfsCheck(*this, i, -1);
            if (a == b)
                return 1;
        }
        return 0;
    }
    void init(int N) { 
        for (int i = 0; i <= N; i++)
            g[i].clear();
        n = 0;
    } 
    int read(int p) {
        int x = ++n;
        char c;
        if (p >= 0)	g[x].push_back(p);
        scanf(" %c%c", &label[x], &c);
        if (c != '(') {
            ungetc(c, stdin);
            return x;
        }
        do {
            g[x].push_back(read(x));
            if (scanf("%c", &c) != 1 || c != ',')
                break;
        } while (true);
        return x;
    }
} tree1, tree2;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        tree1.init(256); tree2.init(256);
        tree1.read(-1); tree2.read(-1);
        int same = tree1.equal(tree2);
        puts(same ? "same" : "different");
    }
    return 0;
}
/*
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))
9999
S(Y(Y(O),U(N(S,E,R(D)))))
D(R(N(U(Y(Y(O),S)),S,E)))
*/