【競技プログラミング】AtCoder Beginner Contest 232_C問題

# 問題
https://atcoder.jp/contests/abc232/tasks/abc232_c

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1
1. 入力を受け取り、高橋君のおもちゃのグラフを隣接リストとして構築する。

2. 青木君のおもちゃの接続情報を保存する。

3. 1からNまでの数字の全ての順列を生成する。

4. 各順列に対して以下の処理を行う：
   a. 順列に基づいて青木君のグラフの頂点を並べ替える。
   b. 並べ替えたグラフが高橋君のグラフと一致するかチェックする。

5. 一致する順列が見つかった場合は「Yes」を出力し、プログラムを終了する。

6. 全ての順列を試しても一致するものが見つからなかった場合は「No」を出力する。


# ACコード1
```python:ac.py
import itertools

def io_func():
    # 頂点数nと辺数mを入力として受け取る
    n, m = map(int, input().split())
    
    # 高橋君のグラフを隣接リストとして構築
    graph1 = [set() for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1  # 0-indexedに変換
        graph1[a].add(b)
        graph1[b].add(a)
    
    # 青木君のおもちゃの接続情報を保存
    cd = [list(map(int, input().split())) for _ in range(m)]
    
    return n, m, graph1, cd

def solve(n, m, graph1, cd):
    # 1からNまでの数字の全ての順列を生成
    for perm in itertools.permutations(range(n)):
        # 順列に基づいて青木君のグラフの頂点を並べ替える
        di = {i: perm[i] for i in range(n)}
        ngraph2 = [set() for _ in range(n)]
        for c, d in cd:
            c, d = c-1, d-1  # 0-indexedに変換
            ngraph2[di[c]].add(di[d])
            ngraph2[di[d]].add(di[c])
        
        # 並べ替えたグラフが高橋君のグラフと一致するかチェック
        if ngraph2 == graph1:
            return "Yes"
    
    # 一致する順列が見つからなかった場合
    return "No"

# メイン処理
n, m, graph1, cd = io_func()
result = solve(n, m, graph1, cd)
print(result)

###
# n: 頂点の数
# m: 辺の数
# graph1: 高橋君のグラフを表す隣接リスト
# cd: 青木君のおもちゃの接続情報
# perm: 頂点の順列
# di: 順列に基づく頂点の対応関係を表す辞書
# ngraph2: 並べ替えた青木君のグラフ

# 1. io_func関数:
#    - 入力を受け取り、高橋君のグラフと青木君の接続情報を構築する
#    - 返り値: n, m, graph1, cd
# 2. solve関数:
#    - 全ての可能な頂点の順列を生成し、各順列に対して以下を行う:
#      a. 青木君のグラフを順列に基づいて並べ替える
#      b. 並べ替えたグラフが高橋君のグラフと一致するかチェックする
#    - 一致する順列が見つかれば "Yes" を返す
#    - 一致する順列が見つからなければ "No" を返す
# 3. メイン処理:
#    - io_func関数を呼び出して入力を処理
#    - solve関数を呼び出して結果を得る
#    - 結果を出力する

```
## オブジェクト指向版1
```python:ac_object.py
import itertools
import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

class InputHandler:
    @staticmethod
    def get_input():
        # 頂点数nと辺数mを入力として受け取る
        n, m = map(int, input().split())
        
        # 高橋君のグラフを隣接リストとして構築
        graph1 = [set() for _ in range(n)]
        for _ in range(m):
            a, b = map(int, input().split())
            a, b = a-1, b-1  # 0-indexedに変換
            graph1[a].add(b)
            graph1[b].add(a)
        
        # 青木君のおもちゃの接続情報を保存
        cd = [list(map(int, input().split())) for _ in range(m)]
        
        return n, m, graph1, cd

class OutputHandler:
    @staticmethod
    def print_result(result):
        print(result)

class Graph:
    def __init__(self, n):
        self.n = n
        self.adjacency_list = [set() for _ in range(n)]

    def add_edge(self, a, b):
        self.adjacency_list[a].add(b)
        self.adjacency_list[b].add(a)

    def __eq__(self, other):
        return self.adjacency_list == other.adjacency_list

    def __str__(self):
        return "".join([f"{i}: {sorted(neighbors)}" for i, neighbors in enumerate(self.adjacency_list)])

class GraphIsomorphismSolver:
    def __init__(self, debug_mode=False):
        self.logger = setup_logger(debug_mode)

    def solve(self, n, m, graph1, cd):
        self.logger.debug("グラフ同型性判定を開始します")
        self.logger.debug(f"[n={n}, m={m}, graph1={graph1}, cd={cd}]")
        # 1からNまでの数字の全ての順列を生成
        for perm in itertools.permutations(range(n)):
            self.logger.debug(f"順列 {perm} を試行中")
            # 順列に基づいて青木君のグラフの頂点を並べ替える
            di = {i: perm[i] for i in range(n)}
            ngraph2 = Graph(n)
            for c, d in cd:
                c, d = c-1, d-1  # 0-indexedに変換
                ngraph2.add_edge(di[c], di[d])
            self.logger.debug(f"ngraph2: {ngraph2}")
            # 並べ替えたグラフが高橋君のグラフと一致するかチェック
            if ngraph2 == graph1:
                self.logger.debug("一致する順列が見つかりました")
                return "Yes"
        
        # 一致する順列が見つからなかった場合
        self.logger.debug("一致する順列が見つかりませんでした")
        return "No"

class GraphIsomorphismChecker:
    def __init__(self, input_handler, output_handler, solver):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.solver = solver

    def run(self):
        # 入力を処理
        n, m, graph1, cd = self.input_handler.get_input()
        
        # グラフオブジェクトを作成
        takahashi_graph = Graph(n)
        for i, edges in enumerate(graph1):
            for j in edges:
                takahashi_graph.add_edge(i, j)
        
        # 解を求める
        result = self.solver.solve(n, m, takahashi_graph, cd)
        
        # 結果を出力
        self.output_handler.print_result(result)

# メイン処理
if __name__ == "__main__":
    input_handler = InputHandler()
    output_handler = OutputHandler()
    solver = GraphIsomorphismSolver(debug_mode=True)
    checker = GraphIsomorphismChecker(input_handler, output_handler, solver)
    checker.run()
```

### オブジェクト図
![try_AtCoder232.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/32d86527-bef9-4b24-9b49-5f23c4e7ebf2.png)


### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputHandler:
    @staticmethod
    def get_input(filename):
        with open(filename, 'r') as f:
            n, m = map(int, f.readline().split())
            graph1 = [set() for _ in range(n)]
            for _ in range(m):
                a, b = map(int, f.readline().split())
                a, b = a-1, b-1
                graph1[a].add(b)
                graph1[b].add(a)
            cd = [list(map(int, f.readline().split())) for _ in range(m)]
        return n, m, graph1, cd

class FileOutputHandler:
    @staticmethod
    def print_result(result, filename):
        with open(filename, 'w') as f:
            f.write(result)

# メイン処理の修正
if __name__ == "__main__":
    input_handler = FileInputHandler()
    output_handler = FileOutputHandler()
    solver = GraphIsomorphismSolver(debug_mode=True)
    checker = GraphIsomorphismChecker(input_handler, output_handler, solver)
    n, m, graph1, cd = input_handler.get_input("input.txt")
    result = checker.run(n, m, graph1, cd)
    output_handler.print_result(result, "output.txt")
```