2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛——D. 挑战图同构（分量哈希） · znzryb
## 思路讲解
当然，我们首先看到这道题目，会想到暴力。
但是暴力显然不行，先不管这个东西要怎么求，存储上，你存都存不下来。
既然这个暴力是不行的，我们就想到，这个图上面的路径太多了，有什么东西两点之间只有一条路径呢？其实就是树。
那么这种比较复杂的题目，特别是比较复杂的图论题目，一般都要划分阶段。
因此我们就要想，这个，如何把这节点一点一点的加入这个图当中？
可以的，兄弟，是可以的。
我们假设我们现在有一张图，我们可以先把到这张图距离为 i 的点加入进来，再把 i+1 的点加入进来，… 。
我们可以使用 kruskal 进行实现，kruskal 的基本过程就是按从小到大排序，加入到图中，使用并查集判环。
划分阶段其实也很简单，就是两张图把距离为 i 的点加入进来，停住。干一些事情，再继续加入距离为 i+1 的点，… 。
我们把一个中间状态摘出来看，如果原来的图是一样的（同构的），加入进来的点的并查集划分是一样的，那么两张图就是同构的。
这么说有点抽象。比如说蓝色的点是原来的图，红色的点是新加进来的点，不难发现，这两张图是同构的。因为只要并查集划分相同，新点之间的这个 dis 就是 i，老点到新点之间的 dis 也都是 i。
然后我们就来到了最后一个问题，怎么样快速判断（ $O(1)$ ）两个图的并查集划分是相同的那？呃，其实不是那么难的。我们请出我们的老盆友，哈希。
一个联通块的签名可以理解为 有什么点。有什么点的话，我们可以给每个点整一个随机值（mt19937_64），然后一个联通块有什么点，就相当于其所有拥有的点的随机值的异或起来。
把这个好几个联通块组合（异或）起来，就可以得到目前的这个并查集划分状态，然后直接比较这个哈希值即可。
## AC代码
[https://qoj.ac/submission/1415583](https://qoj.ac/submission/1415583)
::: 源代码
```cpp
// by Gospel_rock
#include <algorithm>
#include <functional>
#include <random>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e5 + 10,
INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
const ll PI = ll(pi * 2e18) + 71;
ll N, M1, Q, X, K, T, lT, M2;
struct Edge {
ll u, v, w;
// bool operator<(const Edge &other) const {
// return w>other.w;
// }
};
mt19937_64 rng(time(0));
ll rnd[MAXN];
hash<ll> hasher;
const ll RAN = rng();
ll mix(ll a, ll b) {
ll res = (a ^ (b * RAN)) * PI;
return res;
}
struct DSU {
vll fa;
ll N;
vll siz;
ll S;
vll Sum;
void resize(ll n) {
this->N = n;
fa.resize(N + 5);
siz.resize(N + 5);
Sum.resize(N + 5);
S = 0;
FOR(i, 1, N) {
fa[i] = i;
siz[i] = 1;
Sum[i] = rnd[i];
S ^= mix(Sum[i], siz[i]);
}
}
ll find(ll x) {
if (x == fa[x])
return x;
return fa[x] = find(fa[x]);
}
void merge(ll a, ll b) {
ll faa = find(a), fab = find(b);
if (faa == fab) return;
S ^= mix(Sum[faa], siz[faa]);
S ^= mix(Sum[fab], siz[fab]);
fa[faa] = fab;
siz[fab] += siz[faa];
Sum[fab] ^= Sum[faa];
S ^= mix(Sum[fab], siz[fab]);
return;
}
};
struct Solve {
vll fa;
vector<Edge> edge1, edge2;
vll li;
vector<vector<Edge>> g1;
vector<vector<Edge>> g2;
ll get(ll x) {
ll res = lower_bound(all(li), x) - li.begin();
return res;
}
DSU a, b;
Solve() {
cin >> N >> M1 >> M2;
fa.resize(N + 5);
edge1.resize(M1);
edge2.resize(M2);
a.resize(N);
b.resize(N);
FOR(i, 1, N) { fa[i] = i; }
FOR(i, 1, M1) {
ll u, v, w;
cin >> u >> v >> w;
edge1[i - 1] = {u, v, w};
li.PB(w);
}
FOR(i, 1, M2) {
ll u, v, w;
cin >> u >> v >> w;
edge2[i - 1] = {u, v, w};
li.PB(w);
}
// sort(all(edge1));
// sort(all(edge2));
sort(all(li));
li.resize(unique(all(li)) - li.begin());
g1.resize(SZ(li) + 5);
g2.resize(SZ(li) + 5);
FOR(i, 1, M1) { g1[get(edge1[i - 1].w)].PB(edge1[i - 1]); }
FOR(i, 1, M2) { g2[get(edge2[i - 1].w)].PB(edge2[i - 1]); }
FOR(i, 0, SZ(li) - 1) {
for (auto [u, v, w] : g1[i]) {
a.merge(u, v);
}
for (auto [u, v, w] : g2[i]) {
b.merge(u, v);
}
if (a.S != b.S) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
FOR(i, 0, MAXN - 5) { rnd[i] = rng(); }
while (lT--)
Solve a;
return 0;
}
/*
AC
https://qoj.ac/submission/1415583
*/
```
:::
## 心路历程（WA，TLE，MLE……）
merge 的逻辑比较复杂，容易写错，之后可以使用，Old，New，这样的命名，避免混淆。
```cpp
void merge(ll a, ll b) {
ll faa = find(a), fab = find(b);
if (faa == fab) return;
S ^= mix(Sum[faa], siz[faa]);
S ^= mix(Sum[fab], siz[fab]);
fa[faa] = fab;
siz[fab] += siz[faa];
Sum[fab] ^= Sum[faa];
S ^= mix(Sum[fab], siz[fab]);
return;
}
```