2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛——D. 挑战图同构（分量哈希）

思路讲解

当然，我们首先看到这道题目，会想到暴力。

但是暴力显然不行，先不管这个东西要怎么求，存储上，你存都存不下来。

既然这个暴力是不行的，我们就想到，这个图上面的路径太多了，有什么东西两点之间只有一条路径呢？其实就是树。

那么这种比较复杂的题目，特别是比较复杂的图论题目，一般都要划分阶段。

因此我们就要想，这个，如何把这节点一点一点的加入这个图当中？

可以的，兄弟，是可以的。

我们假设我们现在有一张图，我们可以先把到这张图距离为 i 的点加入进来，再把 i+1 的点加入进来，… 。

我们可以使用 kruskal 进行实现，kruskal 的基本过程就是按从小到大排序，加入到图中，使用并查集判环。

划分阶段其实也很简单，就是两张图把距离为 i 的点加入进来，停住。干一些事情，再继续加入距离为 i+1 的点，… 。

我们把一个中间状态摘出来看，如果原来的图是一样的（同构的），加入进来的点的并查集划分是一样的，那么两张图就是同构的。

这么说有点抽象。比如说蓝色的点是原来的图，红色的点是新加进来的点，不难发现，这两张图是同构的。因为只要并查集划分相同，新点之间的这个 dis 就是 i，老点到新点之间的 dis 也都是 i。

然后我们就来到了最后一个问题，怎么样快速判断（ $O(1)$ ）两个图的并查集划分是相同的那？呃，其实不是那么难的。我们请出我们的老盆友，哈希。

一个联通块的签名可以理解为 有什么点。有什么点的话，我们可以给每个点整一个随机值（mt19937_64），然后一个联通块有什么点，就相当于其所有拥有的点的随机值的异或起来。

把这个好几个联通块组合（异或）起来，就可以得到目前的这个并查集划分状态，然后直接比较这个哈希值即可。

AC代码

https://qoj.ac/submission/1415583

源代码

// 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，这样的命名，避免混淆。

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