M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) C - Graph Isomorphism

問題の要約
　N個のボールにM本のひもを取り付けたおもちゃが2つある。
　1つのおもちゃには、ボールに1,...,Nと番号が付けられており、i(1<=i<=M)本目のひもはボールAiとボールBiを結んでいる。
　もう1つのおもちゃも同様に、ボールに1,...,Nと番号が付けられており、i(1<=i<=M)本目のひもはボールCiとボールDiを結んでいる。
　それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2つのボールを2本以上の異なるひもが結んでいることはない。
　ここで、2つのおもちゃが同じ形であるかどうか気になる。
　ここで、2つのおもちゃが同じ形であるとは、以下の条件を満たす数列Pが存在することをいう。
　　・Pは(1,...,N)を並べ替えて得られる。
　　・任意の1以上N以下の整数i,jに対し、以下が成り立つ。
　　　　1つ目のおもちゃにおいてボールi,jがひもで繋がれていることと、2つ目のおもちゃにおいてボールPi,Pjがひもで繋がれていることは同値である。
　2つのおもちゃが同じ形であるならYes、そうでないならNoと出力しろ。
制約
　1<=N<=8
　0<=M<=N(N-1)/2
　1<=Ai<Bi<=N(1<=i<=M)
　(Ai,Bi)≠(Aj,Bj)(i≠j)
　1<=Ci<Di<=N(1<=i<=M)
　(Ci,Di)≠(Cj,Dj)(i≠j)
入力
　N M
　A1 B1
　...
　AM BM
　C1 D1
　...
　CM DM
考え方
　1,問題文からこのおもちゃは単純グラフで表すことができる。
　2,制約からボールの個数の上限が8と少ないので、c++ならnext_permutationを使えばPの並び替えを全て試すことができそう。
　3,1つ目のおもちゃをG1、2つ目のおもちゃをG2としてグラフで表す。
　4,G2からnext_permutationで作った並び替えを使用してG3を作成。
　5,G1とG3が同じならばYes,G1と全てのG3が違うならばNoを出力。

実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

int main(){
  int N,M;
  cin >> N >>M;
  vector<vector<int>> G1(N);
  vector<vector<int>> G2(N);
  for(int i = 0; i < M; i++){
    int A,B;
    cin >> A >> B;
    G1[A-1].push_back(B-1);
    G1[B-1].push_back(A-1);
  }
  for(int i = 0; i < M; i++){
    int C,D;
    cin >> C >> D;
    G2[C-1].push_back(D-1);
    G2[D-1].push_back(C-1);
  }
  for(int i = 0; i < N; i++){
    sort(G1[i].begin(),G1[i].end());
  }
  for(int i = 0; i < N; i++){
    sort(G2[i].begin(),G2[i].end());
  }
  
  vector<int> perm(N);
  for(int i = 0; i < N; i++){
    perm[i] = i;
  }
  
  bool flag;
  do{
    flag = true;
    map<int,int> mp;
    for(int i = 0; i < N; i++){
      mp[i] = perm[i];
    }
    vector<vector<int>> G3(N);
    for(int i = 0; i < N; i++){
      for(int j = 0; j < G2[i].size(); j++){
        G3[mp[i]].push_back(mp[G2[i][j]]);
      }
    }
    for(int i = 0; i < N; i++){
      sort(G3[i].begin(),G3[i].end());
    }
    for(int i = 0; i < N; i++){
      if(G1[i].size() != G3[i].size()){
        flag = false;
        break;
      }
      for(int j = 0; j < G1[i].size(); j++){
        if(G1[i][j] != G3[i][j]){
          flag = false;
          break;
        }
      }
    }
    if(flag){
     break;
    }
  }while(next_permutation(perm.begin(),perm.end()));
  
  if(flag){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return 0;
}