Truy vấn để kiểm tra xem có thể nối các hộp trong một vòng kết nối trong Chương trình C ++ hay không

Trong bài toán này, chúng ta được cung cấp một số n biểu thị n hộp nằm trên cạnh của một hình tròn. Và có Q truy vấn mỗi truy vấn bao gồm hai số nguyên, a và b. Nhiệm vụ của chúng tôi là tạo một chương trình giải quyết các truy vấn để kiểm tra xem có thể nối các hộp trong một vòng kết nối hay không.

Mô tả sự cố - Để giải quyết từng truy vấn, chúng ta cần kiểm tra khả năng kết nối hộp a và hộp b bằng một thanh sao cho giao của các hộp từ truy vấn cuối cùng không thể bị xáo trộn. Chúng tôi cần in có thể hoặc không thể dựa trên điều kiện.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}}

Đầu ra

Possible
Not possible
Possible

Giải thích

Các đường liền nét là những thanh có thể được kết nối, trong khi đường đứt nét là đường không thể được kết nối.

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là bằng cách tìm lời giải của truy vấn cho mỗi truy vấn, chúng ta sẽ tìm xem các hộp đã cho, hộp a và hộp b có thể được kết nối với nhau hay không. Đối với điều này, chúng tôi cần giữ các giá trị của truy vấn cuối cùng làm điểm tham chiếu và sau đó kiểm tra xem kết nối có khả thi hay không.

Chúng ta hãy xem xét các hộp a và b của truy vấn (i-1) dưới dạng tham chiếu ref1 và ref2. Sau đó, tìm xem điểm a và b có nằm ở hai phía đối diện của thanh hay không.

Đối với điều này, chúng tôi sẽ kiểm tra hai điều kiện,

Điều kiện 1 - if (ref1

Điều kiện 2 - if (ref1

Trong cả hai trường hợp, kết quả sẽ không thể thực hiện được.

#include <iostream>
using namespace std;
int printSolutoin(int n, int a, int b, int ref1, int ref2, int lastConn){
   if(lastConn == 0 && a != b)
      return 1;
      int temp;
   if(a > b){
      temp = a;
      a = b;
      b = temp;
   }
   if(ref1 > ref2){
      temp = ref1;
      ref1 = ref2;
      ref2 = temp;
   }
   if( ( ref1 < a && a < b && b < ref2) )
      return 1;
   if( (ref1 <= a <= ref2) && (ref2 <= b <= n) ) return 0;
   else if( (ref1 <= b <= ref2) && (ref2 <= a <= n) )
      return 0;
      return 0;
      return 1;
}
void solveAllQueries(int n, int q, int query[][2]){
   int lastConn = printSolutoin(n, query[0][0], query[0][1], 0, 0, 0);
   lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   for(int i = 1; i < q; i++){
      lastConn = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1],       lastConn);
      lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   }
}
int main() {
   int n = 6;
   int Q = 3;
   int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
   return 0;
}

Possible
Not Possible
Possible