C++で指定された遷移を通じて最終地点に到達可能かどうかを判定する方法

x軸上にn個の点があり、点同士の間で許可された遷移（移動）のリストが与えられているとします。この遷移のみを使って、開始地点から最終地点に到達できるかどうかを判定するのが本記事のテーマです。

例えば、点x1と点x2の間に遷移が存在する場合、点xからx1とx2の間の任意の中間点へ移動することも、直接x2へ移動することもできます。

問題の例

n = 5、遷移が「0から2」「2から4」「3から5」の3つである場合を考えてみましょう。このとき、出力は「YES」になります。なぜなら、0→2→3→5 という経路が存在するからです。

アルゴリズムの考え方

この問題を解くための手順は以下の通りです。

1. ペアのリストを、各ペアの最初の要素（始点）を基準にソートします。
2. リストの2番目のペアから順に、そのペアの始点が「前のペアの終点」と「現在のペアの終点」の間にあるかどうかを確認します。
3. この条件により、隣接する2つのペアの間に経路がつながっているかどうかを判定できます。
4. 最後に、到達した点が目的地の点であり、開始した点が出発点であるかを確認します。

条件をすべて満たしていれば「YES」を表示し、そうでなければ「NO」を表示します。

実装例（C++コード）

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool isPathPairFound(int n, vector<pair<int, int> > array) {
    sort(array.begin(), array.end());
    int start_point = array[0].first;
    int end_point = array[0].second;
    for (int i = 1; i < n; i++) {
        if (array[i].first > end_point)
            break;
        end_point = max(end_point, array[i].second);
    }
    return (n <= end_point && start_point == 0);
}

int main() {
    vector<pair<int, int> > array;
    array.push_back(make_pair(0, 2));
    array.push_back(make_pair(2, 4));
    array.push_back(make_pair(3, 5));
    if (isPathPairFound(5, array))
        cout << "Path has found";
    else
        cout << "NO Path has found";
}

出力結果

Path has found

コードの解説

このコードでは、まずsort関数を使ってペアのリストを始点の昇順に並べ替えています。その後、変数end_pointを更新しながら各ペアを順に走査し、現在のペアの始点がこれまでに到達可能な範囲を超えていないかをチェックします。範囲が途切れていればループを抜け、最終的にend_pointが目的地n以上であり、かつ始点が0であるかどうかを返します。

このアルゴリズムの計算量は、ソートにO(n log n)、走査にO(n)かかるため、全体としてO(n log n)となります。点の数が多い場合でも効率的に動作する実用的なアプローチです。