AtCoder が提供しているABC（AtCoder Beginner Contest）285 のD問題をC++とPythonで解いてみました。ABC285は、2023年1月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Change Usernames（Difficulty : 663）
問題はリンク先をご覧ください。
グラフの閉路を求める問題でした。AtCoder Problems による Difficulty は 663でした。
解答案
変更前→変更先の文字列の関係を、有向グラフと考えます。入力例2にあるように a → b → c → a のような閉路を持つと変更できません。逆に閉路が無ければ、グラフの末端（葉に近い方）から、処理することができます。
C++ プログラム例（ABC285D）
グラフを map で表現している例としては、ABC277 C問題がありました。この問題は、グラフを string と vector<string> の map で表現しました。
グラフは、DFS（深さ優先探索：Depth-First Search）で探索しました。基本と異なるのは、「訪れたか」を表す bool 型の seen に「訪れきったか」を表す finished を加えました。seen が true で、finished が false であれば、閉路を検出したことになります。
閉路を検出したかを bool 型の変数 is_dected に記憶して、最後に出力をしています。
以下は、C++ プログラムです。ポイントとなる行の背景行を変更しました。
#include <bits/stdc++.h>
using namespace std;
map<string, vector<string>> e;
map<string, bool> seen;
map<string, bool> finished;
bool is_detect;
void dfs(string v)
{
seen[v] = true;
for (auto next_v : e[v]) {
if (seen[next_v]) {
if (!finished[next_v]) {
is_detect = true;
}
} else {
dfs(next_v);
}
}
finished[v] = true;
}
int main()
{
int n;
cin >> n;
vector<string> s(n);
vector<string> t(n);
for (int i = 0; i < n; ++i) {
cin >> s[i] >> t[i];
e[s[i]].push_back(t[i]);
}
is_detect = false;
for (int i = 0; i < n; ++i) {
if (!seen[s[i]]) {
dfs(s[i]);
}
}
if (!is_detect) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC285D）
Python 版も、C++ のプログラムをそのまま移植しました。
"""AtCoder Beginner Contest 285 D"""
import sys
from collections import defaultdict
LIMIT = 10 ** 5
sys.setrecursionlimit(LIMIT)
def dfs(v):
global is_detect
seen[v] = True
for next_v in e[v]:
if seen[next_v]:
if not finished[next_v]:
is_detect = True
else:
dfs(next_v)
finished[v] = True
n = int(input())
s = []
t = []
e = defaultdict(list)
seen = defaultdict(lambda: False)
finished = defaultdict(lambda: False)
for i in range(n):
s_t, t_t = input().split()
s.append(s_t)
t.append(t_t)
e[s_t].append(t_t)
is_detect = False
for i in range(n):
if not seen[s[i]]:
dfs(s[i])
print("Yes" if not is_detect else "No")このプログラムは、Python（3.8.2）では、RE（Runtime Error）判定でした。一方、PyPy3（7.3.0）では、AC 判定となりました。今回は、このプログラムを Python 版として紹介します。
最後に
この問題は、コンテストでは解くことができませんでした。set と map を使って、最終的には、グラフの閉路を求めることに近いことをやっていました。
問題をグラフなどの良く知られているデータ構造に帰着できると、解きやすいことが学べました。
引き続き ABC の問題を紹介していきます。
