C++で指定された遷移を介して最後に到達することが可能かどうかを確認します

x軸上にn個のポイントがあり、ポイント間の許可された平行移動のリストがあるとします。これらのトランザクションのみを介して、開始点から終了に到達できるかどうかを確認します。したがって、点x1とx2の間に平行移動がある場合は、点xからx1とx2の間の任意の中間点に移動するか、直接x2に移動できます。したがって、n =5の場合、トランザクションは0から2、2から4、および3から5になります。その場合、出力はYESになります。 0→2→3→5からのパスがあります。

ペアの最初の要素に従ってリストを並べ替える必要があります。次に、リストの2番目のペアから開始し、ペアの最初の要素が前のペアの2番目の要素と現在のペアの2番目の要素の間にあるかどうかを確認します。この条件は、2つの連続するペアの間にパスがあるかどうかを確認するために使用されます。最後に、到達したポイントが目的のポイントであり、開始したポイントが開始ポイントであるかどうかを確認します。そうである場合はYESを表示し、そうでない場合はNOを表示します。

例

#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