Mã C ++ để kiểm tra tất cả các bóng đèn có thể được bật hay không

Giả sử chúng ta có một số m và một danh sách lồng nhau A với n danh sách con. Coi có m bóng đèn, ban đầu tất cả đều tắt. Có n nút và mỗi nút được kết nối với một số bộ bóng đèn. Vậy A [i] là tập hợp các bóng đèn có thể bật được bằng cách nhấn công tắc thứ i. Chúng ta phải kiểm tra xem chúng ta có thể thắp sáng tất cả các bóng đèn hay không.

Vì vậy, nếu đầu vào giống như A =[[1, 4], [1, 3, 1], [2]]; m =4, thì đầu ra sẽ là True, bởi vì bằng cách nhấn tất cả các công tắc, chúng ta có thể bật tất cả bốn bóng đèn.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Define one set s
for initialize i := 0, when i < size of A, update (increase i by 1), do:
   for initialize j := 0, when j < size of A[i], update (increase j by 1), do:
      insert A[i, j] into s
if size of s is same as m, then:
   return true
Otherwise
   return false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> A, int m){
   set<int> s;
   for (int i = 0; i < A.size(); i++){
      for (int j = 0; j < A[i].size(); j++){
         s.insert(A[i][j]);
      }
   }
   if (s.size() == m)
      return true;
   else
      return false;
}
int main(){
   vector<vector<int>> A = { { 1, 4 }, { 1, 3, 1 }, { 2 } };
   int m = 4;
   cout <<solve(A, m) << endl;
}

Đầu vào

{ { 1, 4 }, { 1, 3, 1 }, { 2 } }, 4

Đầu ra

1