（初級者競プロer向け) グラフDFS問題編 その１

この間グラフDFSの初級編の記事を書きました。
（初心者向け）グラフの実装について - bplain’s blog
（初級者競プロer向け）グラフの探索(DFS)を1から再帰関数で実装する方法 - bplain’s blog

さて次は何やろうと思いましたが、よく考えたらまだグラフDFSの具体的な問題をやっていないことに気づきました。
なので良さそうな問題を一つずつ挙げてやっていきます。難易度はD問題相当になりますが、前に書いたグラフの記事がわかる方ならいけると思います。それでは問題に入っていきましょう。

ABC070　D - Transit Tree Path

今回とりあげるのはこちらの問題。400点というと何か大変そうなイメージがある方もいらっしゃるかもしれませんが、実は正解コードのほとんどの行が入力部分で構成されています。なのでまずは入力部分をきちんと書けるようにしていきましょう。

さて、この問題の答えをほぼ言わないと実装に入れないので、自力で考えたい方はこの先はまだ見ないようにしてください。以下解説です。

解説

まず、今回のような単純な木構造にはとある特徴があります。それはどの頂点も根ノードとすることが出来るという点です。(根ノード：木の一番親の部分)
自分も調べて知ったので、知らなかった人は覚えておきましょう。
そして、改めて問題を考えると実はとても単純で、頂点Kを根として考え、そこからの距離をすべて保存し、Kからx、Kからyの距離を足せば終了です。とてもシンプルですね。
しかし初級者の私たちにとっては実装するのも重要です。やっていきましょう。

1、入力部分の実装を行う

最初に言いましたが、グラフの問題は入力部分だけでもかなりの量となります。とりあえず書いていきましょう。
(わからない方は以前の記事をご覧ください)

#include <iostream>
#include <vector>

using namespace std;

#define ll long long

struct edge {
    int to;
    ll cost;
};

vector<edge> tree[100010];


int main() {
    int N;
    cin >> N;

    for (int i = 0; i < N - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back({ b, c });
        tree[b].push_back({ a, c });
    }

    int Q, K;
    cin >> Q >> K;
    K--;

    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;

    }
}

今回は隣接リストの形。

2、DFSの実装を行う

次にDFSの実装です。必要な引数の確認をしていきます。とりあえず始点Kの番号と、Kからの距離は引数に必要そうです。
これでコードを書きたいところですが、今回は無向グラフで、隣接リストに戻る頂点も取り込んでしまっているため、このままでは途中で親ノードに帰ってきてしまい上手くいきません。
そこで引数に親ノードを取り込んでおきます。そうすることで、もし一つ前の頂点と次の行き先が同じであるならばDFSを行わないように実装することが出来ます。

以下が実装例です。

#include <iostream>
#include <vector>

using namespace std;

#define ll long long

struct edge {
    int to;
    ll cost;
};

vector<edge> tree[100010];
ll cost_k[100010];//Kからのコスト

void dfs(int v, int par, ll dist) {//parは親ノード(一つ前の頂点)
    cost_k[v] = dist;

    for (int i = 0; i < (int)tree[v].size(); i++) {
        if (tree[v][i].to == par)continue;
        dfs(tree[v][i].to, v, dist + tree[v][i].cost);//行き先、今いる頂点、距離
    }
}

int main(void) {
    int N;
    cin >> N;

    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back({ b, c });
        tree[b].push_back({ a, c });
    }
    int Q, K;
    cin >> Q >> K;
    K--;

    dfs(K, -1, 0);//Kに親ノードはないので-1とする

    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << cost_k[x] + cost_k[y] << endl;
    }
}

今回は以上となります。無向グラフのDFSには引数に戻ってくる頂点も必要であると覚えておくといいかもしれません。

よかったらtwitterでふぁぼでもくださいな。