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

[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;
}