グラフDFS問題編 その２ (ABC087-D)

ここら辺から初級者の範囲を抜けると思うのでタイトルから消しております。なんか深いところに入っていっている気分ですね。
今回もとてもいい問題なのでやっていきましょう。取り扱う問題はこちら。

ABC087 D - People on a Line
比較的読みやすい問題だと思います。考えたい方はぜひ考えてみてください。
以下解説です。

解説

1、入力部まで

今回の問題はx軸上に並んでいますが、距離が必要になることからグラフに持ち込めそうです。L-R間のcostと考えれば今までの形で入力出来そうですね。 というわけで入力を行っていきます。

入力までのコード

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, cost;
};

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

    for (int i = 0; i < M; i++) {
        int L, R, D;
        cin >> L >> R >> D;
        L--; R--;
        G[L].push_back({ R,D });
        G[R].push_back({ L,-D });//解法に向きが必要なので負で入力
    }
}

今回は一つの頂点からの総合距離を判定しないといけないので入力が負になっています。深く考えなくても大丈夫です。
後はもはや定番の形となりました。隣接リストは優秀ですね。

2、DFSなどの全探索における強み

DFSなどの全探索の強みとして、すべての頂点に一つのある頂点からの距離を、別の配列を用いて全て保存することが出来ます。(例えば0-3-5なら頂点0からの距離はd[3]やd[5]とすることで保存できる)
よって始点を決めることですべての頂点に始点からの距離を保存することが出来ます。

そして改めて考えると、今回の問題で距離に矛盾が生じるならば、それは二つ以上の頂点から一つの頂点に行くことが出来る状態のみです。これを用いて実装を考えると、連結しているグラフにおいて、その頂点に再び訪れることがあった場合に、距離が矛盾しているか否かだけで解くことが可能です。

ということで頂点0からの全探索を行い、頂点0と連結している部分の全ての全探索を行ってしまいます。そしてたどり着いた頂点に一つ一つフラグを立てます。 もしフラグの立てた頂点に訪れた場合、矛盾の判定をそこで行う必要があるので、保存しておいた一度目の探索の距離と、現在引数に取り込んであるdistを比較すれば正しいかどうかが分かります。これにて頂点0に連結しているすべての頂点の探索は終了するので、以下頂点0に連結していない頂点などに同様に行っていけば答えを出すことが出来ます。

以下実装例です。いつも通りソースコードに解説をまとめておきました。

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, cost;
};

vector<edge> G[200010];
bool vis[100010];
int d[100010];

bool dfs(int v, int dist) {
    if (vis[v]) {
        if (d[v] != dist) {
            return true;
        }
        else {
            return false;
        }
    }
    vis[v] = true;
    d[v] = dist;
    for (int i = 0; i < (int)G[v].size(); i++) {
        if (dfs(G[v][i].to, d[v] + G[v][i].cost)) {
            return true;//その頂点における判定で一つでも矛盾があれば、全てtrueを返して強制終了。
        }
        //何も矛盾が無ければ次のリストを見る。
    }
    return false;//連結している頂点が最後まで探索できたという証。
}

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

    for (int i = 0; i < M; i++) {
        int L, R, D;
        cin >> L >> R >> D;
        L--; R--;
        G[L].push_back({ R,D });
        G[R].push_back({ L,-D });
    }
    for (int i = 0; i < N; i++) {//連結していない頂点があった場合に探索していく
        if (!vis[i] && dfs(i, 0)) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

今回の実装の見どころは、bool型の再帰関数にif文を用いてtrueで返し続ける方法です。再帰関数の強制終了の形として知っておくと役立ちそうです。
といったところで今回は終了です。

最近ちょこちょこグラフの問題を探しているのですが、どれもいい問題で改めてatcoderさんの凄さを感じています。あと調べるたびにグラフのDFSの記事が少ない気がするのでこれからも頑張って書いていこうかなと思っています。
おしまい。