C++에서 무방향 그래프가 주어진 크기의 독립 집합을 포함하는지 확인

컨셉

주어진 무방향 그래프와 관련하여 크기가 l인 독립 집합이 포함되어 있는지 확인합니다. 크기가 독립적인 집합이 있으면 'Yes'를 인쇄하고, 그렇지 않으면 'No'를 인쇄합니다. 그래프에서 독립 집합은 서로 직접 연결되지 않은 정점의 집합으로 정의된다는 점에 유의해야 합니다.

입력

L = 4,
graph = [[1, 0, 1, 0, 0],
[0, 1, 1, 0, 0],[1, 1, 1, 1, 1],
[0, 0, 1, 1, 0],[0, 0, 1, 0, 1]];

출력

Yes

위의 그래프는 크기가 4인 독립적인 집합을 포함합니다(정점 0, 1, 3, 4는 서로 직접 연결되어 있지 않음). 따라서 출력은 '예'입니다.

입력

L = 4,
graph =[[1, 1, 1, 0, 0],[1, 1, 1, 0, 0],[1, 1, 1, 1, 1],[0, 0, 1, 1, 0],[0, 0, 1, 0, 1]];

출력

No

다이어그램에서 위의 그래프는 크기 4의 독립적인 집합을 포함하지 않습니다. 따라서 출력은 '아니오'입니다.

방법

• 처음에는 부울 False 값으로 sol 변수를 초기화합니다.
• 주어진 그래프에서 크기가 L인 가능한 모든 정점 집합을 결정합니다.
• 크기가 l인 독립 집합이 발견되면 sol 값을 True로 변경하고 반환하는 것으로 나타났습니다.
• 그렇지 않으면 다른 가능한 세트를 계속 확인하십시오.
• 마지막으로 sol이 True이면 'Yes'를 출력하고 그렇지 않으면 'No'를 출력합니다.

예시

// C++ code to check if a given graph
// contains an independent set of size k
#include <bits/stdc++.h>
using namespace std;
// Shows function prototype
bool check1(int[][5], vector<int>&, int);
// Shows function to construct a set of given size l
bool func(int graph1[][5], vector<int>&arr1,
int l, int index1, bool sol1[]){
   // Verify if the selected set is independent or not.
   // Used to change the value of sol to True and return
   // if it is independent
      if (l == 0){
         if (check1(graph1, arr1, arr1.size())){
            sol1[0] = true;
            return true;
         }
      }
      else{
         // Now set of size l can be formed even if we don't
         // include the vertex at current index.
         if (index1 >= l){
            vector<int> newvec(arr1.begin(), arr1.end());
            newvec.push_back(index1);
            return (func(graph1, newvec, l - 1,
            index1 - 1, sol1) or
            func(graph1, arr1, l, index1 - 1, sol1));
         }
            // Now set of size l cannot be formed if we don't
         // include the vertex at current index.
         else{
            arr1.push_back(index1);
            return func(graph1, arr1, l - 1,
            index1 - 1, sol1);
         }
      }
   }
   // Shows function to verify if the given set is
   // independent or not
   // arr --> set of size l (contains the
   // index of included vertex)
   bool check1(int graph1[][5], vector<int>&arr1, int n1){
      // Verify if each vertex is connected to any other
         // vertex in the set or not
      for (int i = 0; i < n1; i++)
         for (int j = i + 1; j < n1; j++)
            if (graph1[arr1[i]][arr1[j]] == 1)
            return false;
      return true;
}
// Driver Code
int main(){
   int graph1[][5] = {{1, 0, 1, 0, 0},{0, 1, 1, 0, 0},{1, 1, 1, 1, 1},{0, 0, 1, 1, 0},
      {0, 0, 1, 0, 1}};
      int l = 4;
      vector<int> arr1; // Empty set
      bool sol1[] = {false};
      int n1 = sizeof(graph1) /
      sizeof(graph1[0]);
      func(graph1, arr1, l, n1 - 1, sol1);
      if (sol1[0])
         cout << "Yes" << endl;
      else
         cout << "No" << endl;
      return 0;
}

출력

Yes