모든 전구를 켤 수 있는지 확인하는 C++ 코드

숫자 m과 n개의 하위 목록이 있는 중첩 목록 A가 있다고 가정합니다. m 개의 전구가 있다고 가정하십시오. 처음에는 모두 꺼져 있습니다. n 개의 버튼이 있으며 각각은 전구 세트에 연결되어 있습니다. 따라서 A[i]는 i번째 스위치를 눌러 켤 수 있는 전구 세트입니다. 전구를 모두 켤 수 있는지 확인해야 합니다.

따라서 입력이 A =[[1, 4], [1, 3, 1], [2]]와 같은 경우; m =4이면 모든 스위치를 눌러 4개의 전구를 모두 켤 수 있으므로 출력은 True가 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}

입력

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

출력

1