AtCoder Beginner Contest 204: C – Tourの初心者解説（計算量をおさえたDFS）

問題

問題文

1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。道路 i を通ると都市 Ai から Bi へ移動することができます。都市 Bi から都市 Ai への通行はできません。

どこかの都市からスタートし、0 本以上の道路を使い移動して、どこかの都市をゴールとするような旅行の計画を立てます。

スタート地点とゴール地点の都市の組として考えられるものは何通りありますか？

制約

  • 2 <= N <= 2000
  • 0 <= M <= min(2000, N(N-1))
  • 1 <= Ai, Bi <= N
  • Ai != Bi
  • (A_i, B_i) は相異なる
  • 入力に含まれる値は全て整数である

解説

公式解説はコチラ。

考え方

大まかには以下の二つの考え方でソースコードを書きます。

  • DFS（深さ優先探索）でマップをサーチし、到達可能な都市を探す。
  • 一度探索した都市は探索しないようにして計算量を抑える。

例と具体的解法

例えば以下の例を考えます。都市 3 つ、道路 3 つのパターンです。

N=3, M=3
(A1, B1) = (1, 2)
(A2, B2) = (2, 3)
(A3, B3) = (3, 2)

都市 1 から直接移動可能な都市は都市 2 のみですが、都市 2 から都市 3 にも移動可能なので、スタート地点が都市 1 の場合に到達可能な都市の組み合わせは (1, 1), (1, 2), (1, 3) になります。

以下のようにマップに移動可能な都市を変数に記憶させておいて、DFS で再帰的にサーチすることによって移動可能な都市の数を数え上げることができます。

都市移動可能な都市
都市12
都市23
都市32

さらに、temp 配列に探索済みの都市を true とセットしておき、true のときは改めて探索しないようにすれば、計算量を抑えられます。

ソースコード

#include <bits/stdc++.h>
#include <math.h>

#include <string>
using namespace std;

void dfs(vector<bool>& temp, const vector<vector<int>>& mapg, const int num) {
    if (temp[num] == true) { return; }
    temp[num] = true;
    for (int i:mapg[num]) { dfs(temp, mapg, i); }
}

int main(void) {
    int N, M;
    vector<vector<int>> mapg;
    cin >> N >> M;
    mapg.resize(N);
    for (int i=0; i<M; i++) {
        int A, B;
        cin >> A >> B;
        mapg[A-1].push_back(B-1);
    }

    int sum = 0;
    vector<bool> temp(N, false);
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) { temp[j] = false; }
        dfs(temp, mapg, i);
        for (int j=0; j<N; j++) { if (temp[j] == true) sum++; }
    }
    cout << sum << endl;

    return 0;
}

つまったところ

公式解説では、上記ソースコードの mapg と temp に相当する変数はグローバル変数になっていましたが、私はあまりグローバル変数が好きでないので、関数の引数にしています。

この際、dfs() のAPI 引数を以下のようにしたところ TLE となってしまったので、mapg を参照渡しにしました。

void dfs(vector<bool>& temp, const vector<vector<int>> mapg, const int num) {

値渡しだと配列をコピーしてしまうため、オーバーヘッドが大きくなってしまうみたいですね。大きな配列を API の引数として扱う場合は参照渡しやポインタ渡しをした方がよさそうです。

渡す型のサイズが小さいものであれば問題無いが, サイズの大きな型が引数である場合, そのオブジェクトを構築するための処理時間がかかってしまうので, サイズの大きな型では一般に値渡しは推奨出来ない.

https://qiita.com/agate-pris/items/05948b7d33f3e88b8967

まとめ

マップにして探索する部分や値渡しの部分でつまってしまったので解説記事にしました。お役に立てばうれしいです。

コメント