解題區/解題區 - UVa

UVa 12489 - Combating cancer

contents

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

Problem

求兩個無根樹，請問這兩個樹是否同構。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7
1 2
2 3
3 4
4 5
6 2
7 3
1 2
2 3
3 4
4 5
6 2
7 4
6
1 2
1 3
2 4
2 5
3 6
2 4
5 3
6 4
1 4
5 6

Sample Output

1
2
N
S

Solution

找到樹的最小表示法，用括號來表示一棵樹，則可以對所有的子樹的最小表示法做排序，就可以構成這個樹的最小表示法。一直遞歸下去就可以得到最小表示法。

但是這個最小表示法只能用在有根樹，因此對於無根樹利用拓樸排序找到樹的中心 (一個或者是兩個)。

因此最後相互比較中心的情況。

這一題為了加快可以使用 hash，而把字串比較和排序撇開，但是千萬不要拿不同中心兩個 hash 取最小值，再進行同構比較。原因會發生在於中心的取捨，如果直接定義拓樸最後兩個點作為中心，則有可能一點不是中心，那麼就會造成分析上的錯誤。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int dfsMinExp(int u, int p, vector<int> g[]) {
    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, g));
    }
    sort(branch.begin(), branch.end());
//	string exp = "";
//	for(int i = 0; i < branch.size(); i++)
//		exp += branch[i];	
//	return "(" + exp + ")";	
    int a = 63689, b = 378551;
    int ret = 0;
    branch.push_back(1);
    for(int i = 0; i < branch.size(); i++)
        ret = ret * a + branch[i], a *= b;
    return ret;
}
vector<int> getTreeMinExp(vector<int> g[], int n) {
    if(n == 1)	return vector<int>({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, g));
    ret.push_back(dfsMinExp(topo[idx-2], -1, g));
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, x, y;
    vector<int> g1[65536], g2[65536];
    while(scanf("%d", &n) == 1) {
        for(int i = 1; i <= n; i++)
            g1[i].clear(), g2[i].clear();
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g1[x].push_back(y);
            g1[y].push_back(x);
        }
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g2[x].push_back(y);
            g2[y].push_back(x);
        }
        vector<int> hash1 = getTreeMinExp(g1, n);
        vector<int> hash2 = getTreeMinExp(g2, n);
        int same = 0;
        for(int i = 0; i < hash1.size(); i++)
            for(int j = 0; j < hash2.size(); j++)
                same |= hash1[i] == hash2[j];
        puts(same ? "S" : "N");
//		printf("%d %d\n", hash1, hash2);
    }
    return 0;
}