ABC232 C - Graph Isomorphism C++解答例

AtCoder Beginner Contest 232 C - Graph IsomorphismをC++で解きます。

問題

問題文をAtCoderのページより引用します。

問題文

高橋君と青木君は、それぞれ$N$個のボールに$M$本のひもを取り付けたおもちゃを持っています。
高橋君のおもちゃにおいて、ボールには$1, \ldots, N$と番号が付けられており、$i (1 \leq i \leq M)$本目のひもはボール$A_i$とボール$B_i$を結んでいます。
青木君のおもちゃにおいても同様に、ボールには$1, \ldots, N$と番号が付けられており、$i (1 \leq i \leq M)$本目のひもはボール$C_i$とボール$D_i$を結んでいます。
それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2つのボールを2本以上の異なる紐が結んでいることはありません。
すぬけ君は、2人のおもちゃが同じ形であるかどうか気になっています。
ここで、2人のおもちゃが同じ形であるとは、以下の条件を満たす配列$P$が存在することをいいます。

• $P$は$(1, \ldots, N)$を並び替えて得られる。
• 任意の1以上$N$以下の整数$i, j$に対し、以下が成り立つ。
  • 高橋君のおもちゃにおいてボール$i, j$がひもで繋がれていることと、青木君のおもちゃにおいてボール$P_i, P_j$がひもで繋がれていることは同値である。

2人のおもちゃが同じ形であるならYes、そうでないならNoと出力してください。

制約

• $1 \leq N \leq 8$
• $0 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq A_i < B \leq N(1 \leq i \leq M)$
• $(A_i, B_i) \neq (A_j, B_j) (i \neq j)$
• $1 \leq C_i < D_i \leq N(1 \leq i \leq M)$
• $(C_i, D_i) \neq (C_j, D_j)(i \neq j)$
• 入力はすべて整数である。

解答例

順列全探索を使う

問題文の中で「$(1, \ldots, N)$を並び替えて得られる$P$という配列」という文章があることと、制約条件が$1 \leq N \leq 8$という非常に小さい値になっていることから、順列全探索を行えば良いことが推測できます。

2つのグラフが同じ形かどうか判定する

順列全探索を行う中で、ある順列$P$を得たとき、その$P$を使って2つのグラフが同じ形かどうかを判定する方法を考えます。
といっても、今回の問題では制約が小さいので、問題文に書かれている判定方法をそのまま使えば良いでしょう。

• $P$は$(1, \ldots, N)$を並び替えて得られる。
• 任意の1以上$N$以下の整数$i, j$に対し、以下が成り立つ。
  • 高橋君のおもちゃにおいてボール$i, j$がひもで繋がれていることと、青木君のおもちゃにおいてボール$P_i, P_j$がひもで繋がれていることは同値である。

プログラムに実装するためにもう少し噛み砕いてみると、以下のようになります。

• 2つの整数$i, j$を選ぶ。ここで、$1 \leq i \leq N, 1 \leq j \leq N$である。
• 全ての$(i, j)$において以下の2つの条件が満たされていれば、2つのグラフは同じ形である。
  • 高橋君が持つおもちゃにおいて、ボール$i$とボール$j$がひもで結ばれているとき、青木君が持つおもちゃにおいて、ボール$P_i$とボール$P_j$もひもで結ばれている。
  • 高橋君が持つおもちゃにおいて、ボール$i$とボール$j$がひもで結ばれていないとき、青木君が持つおもちゃにおいて、ボール$P_i$とボール$P_j$もひもで結ばれていない。

順列全探索の中で判定すべきなのは、ボール$i$と$j$(ボール$P_i$と$P_j$)がひもで結ばれているかどうかです。言い換えると、2つのグラフのそれぞれについて、ノード$i$と$j$($P_i$と$P_j$)の間にエッジがあるかどうかです。
それさえ判定できてしまえばこの問題を解くことができます。

プログラム実装例

C++のプログラム実装例を以下に示します。

グラフ問題において、ノード$i$とノード$j$との間にエッジがあるかどうかを何度も判定するようなプログラムを実装する際は、グラフを隣接リストではなく隣接行列で表現した方が良い場合があります。
グラフを隣接行列で表現すると、エッジがあるかどうかを$\mathcal{O}(1)$で求めることができます。

本ソースコードの隣接行列表現では、2つのノード間にエッジが存在しない場合は0、エッジが存在する場合は1を代入しています。
このようにすることで、

• 高橋君が持つおもちゃにおいて、ボール$i$とボール$j$がひもで結ばれているとき、青木君が持つおもちゃにおいて、ボール$P_i$とボール$P_j$もひもで結ばれている。
• 高橋君が持つおもちゃにおいて、ボール$i$とボール$j$がひもで結ばれていないとき、青木君が持つおもちゃにおいて、ボール$P_i$とボール$P_j$もひもで結ばれていない。

の判定を簡潔に表現することができるようになっています。

c.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
int main() {
  int64_t N, M;
  std::cin >> N >> M;
  
  // 高橋君が持っているおもちゃを表すグラフ(0-indexedの隣接行列表現)。
  std::vector<std::vector<int64_t>> takahashi(N, std::vector<int64_t>(N, 0));
  for (int64_t i = 0; i < M; i++) {
    int64_t a, b;
    std::cin >> a >> b;

    takahashi.at(a - 1).at(b - 1) = 1;
    takahashi.at(b - 1).at(a - 1) = 1;
  }
  // 青木君が持っているおもちゃを表すグラフ(0-indexedの隣接行列表現)。
  std::vector<std::vector<int64_t>> aoki(N, std::vector<int64_t>(N, 0));
  for (int64_t i = 0; i < M; i++) {
    int64_t c, d;
    std::cin >> c >> d;
 
    aoki.at(c - 1).at(d - 1) = 1;
    aoki.at(d - 1).at(c - 1) = 1;
  }

  // 探索対象の順列P(0-indexed)。
  std::vector<int64_t> P(N);
  // 0からN - 1の数値で初期化する
  std::iota(P.begin(), P.end(), 0);
 
  // 順列全探索
  bool ok = false;
  do {
    bool is_isomorphism = true;
    // 2つの整数i, jの組を全探索する
    for (int64_t i = 0; i < N; i++) {
      for (int64_t j = 0; j < N; j++) {
        // 片方のグラフにエッジがあるのにもう片方のグラフには無い場合、2つのグラフは同じ形ではない。
        if (takahashi.at(i).at(j) ^ aoki.at(P.at(i)).at(P.at(j))) {
          is_isomorphism = false;
        }
      }
    }
 
    if (is_isomorphism) {
      ok = true;
    }
 
  } while (std::next_permutation(P.begin(), P.end()));
 
  if (ok) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
 
  return 0;
}

実際に提出したコードはこちら。