TIOJ 1214 樹論 之 樹同構測試

Tree Hash

#include<cstdio>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int int64;

const int64 P = 100000000007LL;
const int64 X = 107;
vector<int> tree[2][101];

int64 hasht(int fat, int rt, int index){
    vector<int64> ht;
    for(int lx = 0;lx < tree[index][rt].size();lx++){
        int ind = tree[index][rt][lx];
        if(ind == fat) continue;
        ht.push_back(hasht(rt, ind, index));
    }
    sort(ht.begin(), ht.end());
    int64 XN = 1;
    int64 ret = 23;
    for(int lx = 0;lx < ht.size();lx++){
        ret += ht[lx]*XN;
        ret %= P;
        XN *= X;
        XN %= P;
    }
    return ret^34567;
}
int main()
{
    int n, a, b;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        for(int lx = 0;lx < n;lx++)
            tree[0][lx].clear(), tree[1][lx].clear();
        for(int lx = 0;lx < n-1;lx++){
            scanf("%d %d", &a, &b); a--, b--;
            tree[0][a].push_back(b);
            tree[0][b].push_back(a);
        }
        for(int lx = 0;lx < n-1;lx++){
            scanf("%d %d", &a, &b); a--, b--;
            tree[1][a].push_back(b);
            tree[1][b].push_back(a);
        }
        set<int64> hashv[2];
        for(int li = 0;li < 2;li++)
            for(int lx = 0;lx < n;lx++)
                hashv[li].insert(hasht(-1, lx, li));
        bool same = false;
        for(set<int64>::iterator it = hashv[0].begin(); it != hashv[0].end(); it++)
            if(hashv[1].count(*it))
                same = true;
        puts(same?"Same":"Different");
    }
    return 0;
}