ABC284 E - Count Simple Paths

try-catch DFS を布教したいだけ（twitter を眺めていたら見つけたのでパクっただけなんですが…）

問題

atcoder.jp

N 頂点 M 辺の単純無向グラフが与えられる。各頂点の次数は 10 以下である。 頂点 1 からの単純パスの個数を K とした時、 min(10^{6}, K) を求めよ。

制約

1 \le N \le 2 \times 10^{5}
0 \le M \le min(2 \times 10^{5}, \frac{N(N-1)}{2})

解法

基本的には DFS で頂点 1 から順に辿ったパスの個数をカウントすればよい。
K が 10^{6} を超える場合は当然 10^{6} を出力すればいいが、このようにある時点で答えが確定する場合は try-catch 構文 を用いて例外処理として書くと便利である。

try-catch

基本的な構文は以下の通りである：

    try {
        // ここに実行する処理を記述
    } catch (<例外の型> e) { // 例外が投げられた場合（throw で例外を投げることができる）
        // 例外が投げられた場合の処理を記述
    }

try ブロック内で実行した内容で受け取れる例外が発生した場合、即座に catch ブロック内の処理が実行される。 これを用いることで、再帰関数内で答えが確定した時に即座に答えを出力してプログラムを終了させることができる。具体的には、以下のように実装すればよい：

    auto dfs = [&](auto &&dfs, <dfs の引数>) -> void {
        if (<答えが確定した場合>) {
            // 答えを出力
            throw 0; // ここで例外を投げる
        }
        // dfs の処理を書く
    };
    try {
        dfs(dfs, <dfs の初期状態の引数>);
    } catch (int e) { // ここで例外を受け取る
        return 0;  // プログラムを終了する
    }

プログラムを即座に終了させるだけなら exit(0) などの手段があるが、例えばマルチテストケースの場合に exit(0) だと困ってしまう一方で、try-catch だと拡張が簡単である。

またこの手法を用いることで、次数が 10 以下という制約が無くとも簡単に問題を解くことができる。

ちなみに、自分は以下のようなマクロをテンプレートに定義している：

#define TRYDFS(dfs)   \
    try {             \
        dfs;          \
    } catch (int e) { \
        return 0;     \
    }

提出

atcoder.jp

#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    // DFS 10^6 を超えた時点で例外処理として 10^6 を出力して終了
    int ans = 0;
    constexpr int MAX = 1000000;
    constexpr int N = 200000;
    bitset<N> reach(0);
    auto dfs = [&](auto &&dfs, int v) -> void {
        if (ans >=
            MAX) {  // 答えが確定した場合（ここでは、K が 10^6 を超えた場合）
            cout << MAX << "\n";  // ここで答えを出力
            throw 0;              // ここで例外を投げる
        }
        ans++;
        reach[v] = 1;
        for (int to : g[v]) {
            if (not reach[to]) {
                dfs(dfs, to);
            }
        }
        reach[v] = 0;
    };
    try {
        dfs(dfs, 0);
    } catch (int e) {  // ここで例外を受け取る
        return 0;      // プログラムを終了する
    }

    // 答えの出力
    cout << ans << "\n";
}

感想

try-catch DFS を用いて穏やかな生活へ