[51Nod1676 无向图同构]无向图哈希[通俗易懂]

[51Nod1676无向图同构]无向图哈希分类:DataStructureHash1.题目链接[51Nod1676无向图同构]2.题意描述3.解题思路对某一个东西进行哈希,一般就选取一些特征点,然后尽可能离散化这些特征点。对于无向图中的每一个联通块来说,他的特征点就是顶点的度。显然这样还不够,那么可以加入深度这个特征,只需要对联通块的每一个顶点bfs求一边单源点最短路。利用这两个特

大家好,又见面了,我是你们的朋友全栈君。

[51Nod1676 无向图同构]无向图哈希

分类:Data Structure Hash

1. 题目链接

[51Nod1676 无向图同构]

2. 题意描述

题目描述

3. 解题思路

对某一个东西进行哈希,一般就选取一些特征点,然后尽可能离散化这些特征点。对于无向图中的每一个联通块来说,他的特征点就是顶点的度。显然这样还不够,那么可以加入深度这个特征,只需要对联通块的每一个顶点bfs求一边单源点最短路。
利用这两个特征点,然后随意构造哈希函数(xjb搞)就可以了。不过代码写得并不优美

4. 实现代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double lb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> puu;
typedef pair<lb, lb> pbb;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
template<typename T> inline void umax(T &a, T b) { a = max(a, b); }
template<typename T> inline void umin(T &a, T b) { a = min(a, b); }
template<typename T> inline T randIntv(const T& a, const T& b) { return (T)rand() % (b - a + 1) + a; }
void debug() { cout << endl; }
template<typename T, typename ...R> void debug (T f, R ...r) { cout << "[" << f << "]"; debug (r...); }

const int MAXN = 500;
const int BASE1 = 13331;
const int BASE2 = 100007;
vector<int> G1[MAXN], G2[MAXN];
int dep[MAXN], du1[MAXN], du2[MAXN];
ull qz1[100000], qz2[100000];
ull bfs(int s, vector<int> G[], int du[]) {
    memset(dep, -1, sizeof(dep));
    ull ret1 = 0, ret2 = 0;
    queue<int> q;
    q.push(s);
    dep[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ret1 += qz1[du[u]];
        ret2 += qz2[dep[u]];
        for (auto& v : G[u]) {
            ret1 += (qz1[du[u]] * qz1[du[v]]);
            ret2 += (qz2[dep[u]] * qz2[dep[v]]);// ^ (qz1[du[u]] * qz1[du[v]]); // * qz2[dep[u]] * qz2[dep[v]];
            if (dep[v] != -1) continue;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
    return ret1 ^ ret2;
}
bool used[MAXN];
vector<int> path;
void dfs(int u, vector<int> G[]) {
    if (used[u]) return;
    used[u] = true;
    path.push_back(u);
    for (auto& v : G[u]) {
        dfs(v, G);
    }
}

void hashV(int n, vector<int> G[], int du[], vector<ull>& ret) {
    memset(used, false, sizeof(used));
    ret.clear();
    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        path.clear();
        dfs(i, G);
        ull temp = 0;
        for (auto& u : path) temp += bfs(u, G, du);
        ret.push_back(temp * qz2[path.size()]);
    }
    sort(ret.begin(), ret.end());
}

int main() {
#ifdef ___LOCAL_WONZY___
    freopen("input.txt", "r", stdin);
#endif // ___LOCAL_WONZY___
    qz1[0] = qz2[0] = 1;
    for (int i = 1; i < 100000; ++i) {
        qz1[i] = qz1[i - 1] * BASE1;
        qz2[i] = qz2[i - 1] * BASE2;
    }
    int T, n, m, u, v;
    cin >> T;
    while (T --) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            G1[i].clear();
            G2[i].clear();
            du1[i] = du2[i] = 0;
            dep[i] = -1;
        }
        for (int i = 1; i <= m; ++i) {
            cin >> u >> v;
            G1[u].push_back(v);
            G1[v].push_back(u);
            ++ du1[u]; ++ du1[v];
        }
        for (int i = 1; i <= m; ++i) {
            cin >> u >> v;
            G2[u].push_back(v);
            G2[v].push_back(u);
            ++ du2[u]; ++ du2[v];
        }
        vector<ull> v1, v2;
        hashV(n, G1, du1, v1);
        hashV(n, G2, du2, v2);
        bool ans = equal(v1.begin(), v1.end(), v2.begin());
        cout << (ans ? "YES" : "NO") << endl;
    }
#ifdef ___LOCAL_WONZY___
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << "ms." << endl;
#endif // ___LOCAL_WONZY___
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/127907.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 详解贝叶斯学派与频率学派的区别和联系

    详解贝叶斯学派与频率学派的区别和联系大家好,我是东哥。要说贝叶斯和频率学派,那简直太有意思了。为什么这么说呢?因为两个学派的理解对于我来说真的是一场持久战。我是在学习机器学习的时候接触到的这两个学派,此前并不知道,当时就被深深吸引了,于是找了各种资料学习下来,说实话感觉有点懂了,但又感觉没理解透。后面我一直是带着这种似懂非懂的状态继续肝机器学习。但随着不断深入学习我发现很多理论其实都有出现两个学派的身影,而且在模型算法层面结合两派不断琢磨对我的理解有了很大帮助,经常有茅塞顿开的感觉(那段日子真的进步的飞起)。虽说我有点笨,但好在经过时间

  • 深度神经网络总结

    深度神经网络总结深度神经网络(DeepNeuralNetworks,DNN)可以理解为有很多隐藏层的神经网络,又被称为深度前馈网络(DFN),多层感知机(Multi-Layerperceptron,MLP)。1前向传播算法1.1从感知机到神经网络感知机的模型是一个有若干输入和一个输出的模型,如下图:输出和输入之间学习到一个线性关系,得到中间输出结果:接着是一个神经元激活函数,…

  • 关于easy的短语(facemock框架)

    作为一个月薪3000的屌丝民工,今天也开始写自己的微博了,打发一下dota之外的时光。写了一年的flex,虽然很是熟练,但是有啥用呢。新版flash的普及上不去,旧版的渲染太慢。还是改行好了。最近开始研究有啥好的东西,之前看了一下unity3d,但是发现自己得先去学3dmax,可是看了3dmax发现高手实在太多了。要学好也不知道要多久,况且自己的美术功底实在太差。专研一下后台吧,发现自己编码解码不

  • CultureInfo中重要的InvariantCulture[通俗易懂]

    CultureInfo中重要的InvariantCulture[通俗易懂]CultureInfo简述CultureInfo类位于System.Globalization命名空间内,这个类和这个命名空间许多人都不了解也认为不需要太多了解,实际上,你写的程序中会经常间接得使用这些类。简单的说:当进行数字,日期时间,字符串匹配时,都会进行CultureInfo的操作,也就是不同的CultureInfo下,这些操作的结果可能会不一样。这里要介绍一下非常容易被忽视的In…

  • mac ntfs 读写操作[通俗易懂]

    mac ntfs 读写操作[通俗易懂]发现mac系统无法对ntfs盘进行写操作,找到了解决办法,这里做个记录。1、在spotlight(就是那个放大镜图标)中输入“终端”二字,然后按enter。2、打开终端后输入diskutillist查看所有分区的卷标。[MacxdeMacBook-Pro:~Macx$diskutillist/dev/disk0(internal,physical):#:…

  • mysql中字符转数字_MySQL字符串与数字互转

    mysql中字符转数字_MySQL字符串与数字互转MySQL获得当前系统日期时间函数01.获得当前日期+时间(date+time)函数:now()SELECTNOW();–2010-04-1517:55:3902.获得当前日期(date)函数:curdate()SELECTCURDATE();–2010-04-1503.获得当前时间(time)函数:curtime()SELECTCURTIME();–1…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号