离散数学输入两个有向图的邻接矩阵判断同构的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], ina[MAXN], inb[MAXN], outa[MAXN], outb[MAXN]; // 存储节点出度和入度的数组
    memset(da, 0, sizeof(da));
    memset(db, 0, sizeof(db));
    memset(ina, 0, sizeof(ina));
    memset(inb, 0, sizeof(inb));
    memset(outa, 0, sizeof(outa));
    memset(outb, 0, sizeof(outb));
    for (int i = 0; i < n; i++) {
        int d = 0;
        for (int j = 0; j < n; j++) {
            if (a[i][j]) {
                d++;
                outa[i]++;
                ina[j]++;
            }
        }
        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++;
                outb[i]++;
                inb[j]++;
            }
        }
        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;
            }
        }
    }
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i++) {
        if (ina[i] != inb[i] || outa[i] != outb[i]) return false;
    }
    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] = 1;
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        b[u][v] = 1;
    }
    if (isomorphic()) {
        cout << "两个图同构" << endl;
    } else {
        cout << "两个图不同构" << endl;
    }
    return 0;
}

程序的基本思路和之前的程序类似，不同的是需要分别计算每个节点的入度和出度，并且在比较两个邻接矩阵中每个节点的邻居时，需要分别考虑其出度和入度的邻居。如果两个邻接矩阵同构，则它们具有相同的节点出度和入度序列，并且每个节点的出度和入度的邻居集合也相同。

下面是一个示例输入输出：

输入：

3
0 1 1
1 0 1
1 1 0
0 1 1
1 0 1
1 1 0

输出：

两个图同构

解释：输入的是两个 $3$ 阶有向图的邻接矩阵，分别是：

0 1 1
1 0 1
1 1 0

0 1 1
1 0 1
1 1 0

可以看出这两个图是同构的，因此输出 `两个图同构`。