专栏首页数据结构与算法BZOJ4337: BJOI2015 树的同构(hash 树同构)

BZOJ4337: BJOI2015 树的同构(hash 树同构)

题意

题目链接

Sol

树的同构问题,直接拿hash判一下,具体流程大概是这样的:

首先转化为有根树,预处理出第\(i\)棵树以\(j\)为根时的hash值。

那么两个树同构当且仅当把两棵树的hash数组排完序后完全一致(感性理解一下)

/*

*/
#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long 
#define ull unsigned long long 
using namespace std;
const int MAXN = 51, mod = 1e9 + 7;
const ull base = 997;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, ha[MAXN][MAXN], fa[MAXN], ans[MAXN], top, num[MAXN];
ull st[MAXN], f[MAXN];
vector<int> v[MAXN];
ull dfs(int x, int fa) {
    vector<int> st;   
    f[x] = 1;
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        st.push_back(dfs(to, x));
    }
    sort(st.begin(), st.end());
    for(int i = 0; i < st.size(); i++) f[x] = base * f[x] + st[i];
    return f[x];
}
bool check(int a, int b) {
    if(num[a] != num[b]) return 0;
    for(int i = 1; i <= num[a]; i++)
        if(ha[a][i] != ha[b][i]) return 0;
    return 1;
}
signed main() {
    N = read();
    for(int i = 1; i <= N; i++) {
        num[i] = read();
        for(int j = 1; j <= num[i]; j++) v[j].clear();
        for(int j = 1; j <= num[i]; j++) {
            fa[j] = read();
            if(fa[j]) v[fa[j]].push_back(j), v[j].push_back(fa[j]);
        }
        for(int j = 1; j <= num[i]; j++)
            ha[i][j] = dfs(j, 0);
        sort(ha[i] + 1, ha[i] + num[i] + 1);
    }
    for(int i = 1; i <= N; i++) {
        ans[i] = i;
        for(int j = 1; j <= i - 1; j++) 
            if(check(j, i)) {ans[i] = j; break;}
    }
    for(int i = 1; i <= N; i++) printf("%d\n", ans[i]);
    return 0;
}
/*
4 
4 2 0 2 3 
4 0 1 1 2
4 0 1 1 1 
4 0 1 2 3 
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1576 最长严格上升子序列

    1576 最长严格上升子序列  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给...

    attack
  • 1008 选数 2002年NOIP全国联赛普及组

    1008 选数 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 ...

    attack
  • BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

    attack
  • 1576 最长严格上升子序列

    1576 最长严格上升子序列  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给...

    attack
  • MCU SPI屏也能跑这么炫酷的特效?来,移植起来秀一秀

    最近智能小车的项目还在加功能调试中,等后续调试完毕后更文。今天咱们就来分享一个在Github上看到的非常有意思的GUI开源项目。

    morixinguan
  • 生成1~n的排列(模板),生成可重集的排列(对应紫书P184, P185)

    _DIY
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键
  • 2016计蒜之道复赛 百度地图的实时路况(Floyd 分治)

    首先一个结论:floyd算法的正确性与最外层\(k\)的顺序无关(只要保证是排列即可)

    attack
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • P1197 [JSOI2008]星球大战

    题目描述 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几...

    attack

扫码关注云+社区

领取腾讯云代金券