ABC232:C - Graph Isomorphismの解法メモ

問題の本質

この問題は

「2つのグラフが同一か？」 ではなく 「頂点番号を無視したとき、同じ形か？」 を聞いている

つまり

• 頂点番号は意味を持たない
• 番号の付け替え（＝置換）が許されている

ここで「ラベル付きグラフ」ではなく、　「ラベルなしグラフ（同型判定）」　だと気づくのが第一段階。

なぜ BFS / DFS ではダメそうか？

一見の発想

• BFS/DFSで探索木を作る
• 形が同じなら同型？

ここで違和感

• BFS/DFSの結果は
  • 探索開始点
  • 隣接頂点を見る順番 に依存する
• 同じグラフでも、番号が違えば探索順は変わる

「探索結果が一致する」条件を作るのが難しい
→ BFS/DFSは判定の“道具”として不安定

次数を見る発想

思いつきやすい条件

• 「対応する頂点の次数が一致していれば良さそう」

ここでの気づき

• 次数一致は 必要条件
• でも次数列が同じでも非同型なグラフは存在する

局所情報（次数）だけでは足りない

発想の転換：番号を「決め打ち」してみる

ここで考え方をひっくり返す。

「正しい対応関係が分からないなら、 全部試せばいいのでは？」

問題文の制約を見る

• N ≤ 8

頂点の並び替えは最大でも、8! = 40320 通りのため全探索が現実的

置換 p の意味

• p[i] =「グラフAの頂点 i に対応する、グラフBの頂点」

置換 p が正しければ：

$A に辺 (i, j) がある ⇔B に辺 (p[i], p[j]) がある$

これが すべての (i, j) で成り立つ。

辺の有無そのものを完全一致で比較するという、最も素直で強い条件。

なぜ隣接行列が向いているか

隣接リストだと

• 「辺があるか？」の確認が面倒

隣接行列なら：

gA[i][j] == gB[p[i]][p[j]]

が O(1) で書ける。

置換 × 全ペア確認 という構造にピッタリ。

最終的な思考フロー

1. 頂点番号は意味を持たない
2. BFS/DFSは探索順に依存する → 判定が難しい
3. 次数一致は必要だが不十分
4. N が小さい → 置換全探索が可能
5. 「正しい対応」を仮定して辺の有無を完全比較
6. 1つでも成立すれば Yes

まとめ

この問題は「頂点番号を無視したグラフ同型判定」であり、BFS/DFS では探索順に依存するため判定条件を作りにくい。

N≤8 と小さいため、頂点の対応関係を置換として全列挙し、各置換について「辺の有無が完全に一致するか」を調べることで確実に同型判定ができる。

解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    int a, b;
    vector<vector<int>> gA(N, vector<int>(N, 0));
    vector<vector<int>> gB(N, vector<int>(N, 0));
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        a--;
        b--;
        gA[a][b] = gA[b][a] = 1;
    }
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        a--;
        b--;
        gB[a][b] = gB[b][a] = 1;
    }
    vector<int> p(N);
    for (int i = 0; i < N; i++) {
        p[i] = i;
    }
    do {
        bool ok = true;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (gA[i][j] != gB[p[i]][p[j]]) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            cout << "Yes";
            return 0;
        }
    } while (next_permutation(p.begin(), p.end()));
    cout << "No";
    return 0;
}