C++에서 주어진 전환을 통해 끝에 도달할 수 있는지 찾기

x축에 n개의 점이 있고 점 사이에 허용되는 변환 목록이 있다고 가정합니다. 이러한 거래를 통해서만 출발점에서 끝점에 도달할 수 있는지 알아보십시오. 따라서 점 x1과 x2 사이에 변환이 있는 경우 점 x에서 x1과 x2 사이의 중간 점으로 또는 직접 x2로 이동할 수 있습니다. 따라서 n =5이면 트랜잭션은 0에서 2, 2에서 4, 3에서 5입니다. 그러면 출력은 YES입니다. 0→2→3→5 경로가 있습니다.

쌍의 첫 번째 요소에 따라 목록을 정렬해야 합니다. 그런 다음 목록의 두 번째 쌍에서 시작하여 쌍의 첫 번째 요소가 이전 쌍의 두 번째 요소와 현재 쌍의 두 번째 요소 사이에 있는지 확인합니다. 이 조건은 두 개의 연속 쌍 사이에 경로가 있는지 확인하는 데 사용됩니다. 마지막으로 도달한 지점이 목적지 지점인지, 출발 지점이 시작 지점인지 확인합니다. 그렇다면 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