問題
既存投稿一覧ページへのリンク
解法手順1
-
入力を受け取り、高橋君のおもちゃのグラフを隣接リストとして構築する。
-
青木君のおもちゃの接続情報を保存する。
-
1からNまでの数字の全ての順列を生成する。
-
各順列に対して以下の処理を行う：
a. 順列に基づいて青木君のグラフの頂点を並べ替える。
b. 並べ替えたグラフが高橋君のグラフと一致するかチェックする。 -
一致する順列が見つかった場合は「Yes」を出力し、プログラムを終了する。
-
全ての順列を試しても一致するものが見つからなかった場合は「No」を出力する。
ACコード1
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
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()
オブジェクト図
オブジェクト指向版1で書くメリット
拡張性と再利用性
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")