[51nod1676 undirected graph isomorphism] undirected graph hash [easy to understand]

Hello everyone , I meet you again , I'm your friend, Quan Jun .

[51Nod1676 Undirected graphs are isomorphic ] Undirected graph hash

classification ：Data StructureHash

1. Topic link

[51Nod1676 Undirected graphs are isomorphic ]

2. Description of the question

3. Their thinking

Hash something , Generally, some feature points are selected , Then discretize these feature points as much as possible . For every connected block in an undirected graph , His characteristic is The degree of the vertex . Obviously, this is not enough , Then you can add depth This feature , Just connect each vertex of the block bfs Find the shortest path of single source point on one side . Use these two feature points , Then arbitrarily construct hash function （xjb To make ） That's all right. . But the code is not beautifully written

4. Implementation code

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

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/127907.html Link to the original text ：https://javaforall.cn