离散数学输入两个无向图或有向图的邻接矩阵判断同构的c++程序

以下是一个简单的 C++ 程序，可用于判断两个无向图或有向图的邻接矩阵是否同构：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100;

int n, m; // n 表示图中的节点数，m 表示图中的边数
int a[MAXN][MAXN]; // 存储第一个图的邻接矩阵
int b[MAXN][MAXN]; // 存储第二个图的邻接矩阵
bool vis[MAXN]; // 标记数组，用于深度优先搜索

// 判断两个邻接矩阵是否同构
bool isomorphic() {
    vector<int> va, vb; // 存储节点度数的数组
    int da[MAXN], db[MAXN]; // 存储节点度数的数组
    memset(da, 0, sizeof(da));
    memset(db, 0, sizeof(db));
    for (int i = 0; i < n; i++) {
        int d = 0;
        for (int j = 0; j < n; j++) {
            if (a[i][j]) d++;
        }
        da[d]++;
        va.push_back(d);
    }
    for (int i = 0; i < n; i++) {
        int d = 0;
        for (int j = 0; j < n; j++) {
            if (b[i][j]) d++;
        }
        db[d]++;
        vb.push_back(d);
    }
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
    for (int i = 0; i < n; i++) {
        if (da[i] != db[i]) return false;
    }
    for (int i = 0; i < n; i++) {
        if (va[i] != vb[i]) return false;
    }
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vector<int> v1, v2;
            for (int j = 0; j < n; j++) {
                if (a[i][j]) v1.push_back(j);
                if (b[i][j]) v2.push_back(j);
            }
            sort(v1.begin(), v1.end());
            sort(v2.begin(), v2.end());
            if (v1 != v2) return false;
            for (int j = 0; j < v1.size(); j++) {
                vis[v1[j]] = true;
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        a[u][v] = a[v][u] = 1;
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        b[u][v] = b[v][u] = 1;
    }
    if (isomorphic()) {
        cout << "两个图同构" << endl;
    } else {
        cout << "两个图不同构" << endl;
    }
    return 0;
}

程序的基本思路是先计算每个节点的度数，然后将它们按照度数从小到大排序，最后分别比较两个邻接矩阵中每个节点的邻居是否相同。如果两个邻接矩阵同构，则它们具有相同的节点度数序列，并且每个节点的邻居集合也相同。