AtCoder が提供しているABC（AtCoder Beginner Contest）277 のC問題をC++とPythonで解いてみました。ABC277は、2022年11月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Ladder Takahashi（Difficulty : 540）
問題はリンク先をご覧ください。
ビルの階数の問題ですが、グラフを使って解きます。AtCoder Problems による Difficulty は、540 でした。
解答案
問題を解く方針を書きだします。
- 階を頂点、はしごを辺と考えて、グラフとして読み込む。
- 1階と連結しているもっとも高い階を探索する。
- 結果を出力する。
C++ プログラム例（ABC277C）
グラフの表現については、こちらで解説しました。今回は、頂点の範囲が $1 \leqq$ 頂点 $\leqq 10^9$ であるため、map を使ってグラフを表現します。
1階と連結している頂点は、DFS（深さ優先探索：Depth-First Search）で探索します。探索には、BFS（幅優先探索：Breadth-First Search）を使ってもよいです。一般的に BFS では、キューを使います。
以下は、DFS を再帰関数として実装しました。解（もっとも高い階）を result として保持しています。より高い階に至れば、result を更新します。最後に result を出力します。
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int>> e;
map<int, bool> seen;
int result = 1;
void dfs(int v)
{
seen[v] = true;
if (v > result) {
result = v;
}
for (auto next_v : e[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1);
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC277C）
2022年11月28日
当初、Python 版は、RE（Runtime Error）と判定されるテストケースが出ました。理由が分からず紹介していませんでした。理由が判明したため、以下を追記します。
最初に RE（Runtime Error）と判定されたプログラムを紹介します。基本的に C++ 版の移植です。
"""AtCoder Beginner Contest 277 C"""
from collections import defaultdict
def dfs(v):
seen[v] = True
result.append(v)
for next_v in e[v]:
if not seen[next_v]:
dfs(next_v)
e = defaultdict(list)
seen = defaultdict(lambda: False)
result = [1]
n = int(input())
for i in range(n):
a, b = map(int, input().split())
e[a].append(b)
e[b].append(a)
dfs(1)
print(max(result))RE と判定される理由は、再帰呼び出しの上限回数を超えていたためです。この事情は、問題269 D問題でも紹介していました。
この問題の場合、$1 \leqq N \leqq 2 \times 10^5$ の数だけ、再帰関数が呼び出される可能性があります（すべての階段を通る場合です）。
sys.setrecursionlimit によって再帰呼び出しの上限回数を増やします。この文を追加して、すべてのテストケースで動作するようになりました。
"""AtCoder Beginner Contest 277 C"""
from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(200001)
def dfs(v):
seen[v] = True
result.append(v)
for next_v in e[v]:
if not seen[next_v]:
dfs(next_v)
e = defaultdict(list)
seen = defaultdict(lambda: False)
result = [1]
n = int(input())
for i in range(n):
a, b = map(int, input().split())
e[a].append(b)
e[b].append(a)
dfs(1)
print(max(result))このプログラムは「AC」と判定されました。
最後に
グラフに関係する問題も、いくつか解いているとプログラミングに慣れてきました。今は、グラフの連結している頂点の探索は、（BFSが使える場合も）DFS に決めています。このため、DFS の理解が深まってきたと感じています。
引き続き ABC の問題を紹介していきます。
