Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình tìm 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.
Đối với điều này, chúng tôi sẽ được cung cấp với một vòng tròn các hộp chạy từ 1 đến n. Nhiệm vụ của chúng tôi là tìm xem hộp tôi có thể được kết nối với hộp j bằng một thanh mà không giao nhau giữa các đường trước đó hay không.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
//checking if making a circle from boxes is possible
void isPossible(int n, int q, int queryi[], int queryj[]) {
int arr[50];
for (int i = 0; i <= n; i++)
arr[i] = 0;
for (int k = 0; k < q; k++) {
int check = 0;
if (queryj[k] < queryi[k]) {
int temp = queryi[k];
queryi[k] = queryj[k];
queryj[k] = temp;
}
if (arr[queryi[k]] != 0 || arr[queryj[k]] != 0)
check = 1;
else if (queryi[k] == queryj[k])
check = 1;
else {
for (int i = 1; i < queryi[k]; i++) {
if (arr[i] != 0 && arr[i] < queryj[k] && queryi[k] < arr[i]) {
check = 1;
break;
}
}
if (check == 0) {
for (int i = queryi[k] + 1; i < queryj[k]; i++) {
if (arr[i] != 0 && arr[i] > queryj[k]) {
check = 1;
break;
}
}
}
}
if (check == 0) {
cout << "Possible" << endl;
arr[queryi[k]] = queryj[k];
arr[queryj[k]] = queryi[k];
}
else
cout << "Not Possible" << endl;
}
}
int main() {
int size = 5;
int q = 2;
int queryi[] = { 3, 5 };
int queryj[] = { 1, 4 };
isPossible(size, q, queryi, queryj);
return 0;
} Đầu ra
Possible Possible