msc.cpp

#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=1000;
int counter=0;
int ub;
class bitarray{

public:
int id;
bitset<N> * b;

bitarray(int i){
  id = i;
  b = new bitset<N>;
}

bitarray(const bitarray& c){
  id = c.id;
  b = new bitset<N>;
  if(b==NULL){
    cout<< "DEATH";
    exit(1);
  }
  (*b)|= (*(c.b));
}

int size(){
  return (*b).count();
}
void print(){
  for(int i=0;i<((*b).size());i++){
    cout << ((*b)[i]);
  }
  cout << "\n";
}

void removeAll(const bitarray& a){
  *b &= ~(*(a.b));
}

void add(int i){
  (*b).set(i);
}

int contains(int i){
  return (*b)[i];
}

int containsAll(const bitarray& a){
  if((*b|*(a.b)) == *b){
    return 1;
  }
  return 0;
}
};

void remove_set(bitarray& universe, vector<bitarray>& sets, int pick){
  bitarray r (sets[pick]);
  sets.erase(sets.begin()+pick);
  universe.removeAll(r);
  for(int i=0;i<sets.size();i++){
    sets[i].removeAll(r);
  }
}

void remove_subsets(vector<bitarray>& sets){
  for(int i=0;i<sets.size();i++){
    for(int j=i+1;j<sets.size();j++){
      while(j<sets.size() && sets[i].containsAll(sets[j])){
        sets.erase(sets.begin()+j);
      }
    }
  }
}

vector<bitarray> deep_clone(const vector<bitarray>& sets){
  vector<bitarray> v;
  for(int i=0;i<sets.size();i++){
    bitarray p (sets[i]);
    v.push_back(p);
  }
  return v;
}

int set_sorter(const bitarray& a, const bitarray& c){
  if(((*(a.b)).count())<((*(c.b)).count())){
    return 0;
  }
  return 1;
}

int branch_value(bitarray& universe, vector<bitarray>& sets){
  for(int i=0;i<(*(universe.b)).size();i++){
    if(universe.contains(i)){
      int c = 0;
      int t = 0;
      for(int j =0;j<sets.size();j++){
        if(sets[j].contains(i)){
          t=j;
          c++;
          if(c==2){
            break;
          }
        }
      }
      if(c==0){
        return -2;
      }
      if(c==1){
        return t;
      }
    }
  }
  return -1;
}
void bb(bitarray& universe, vector<bitarray>& sets, vector<int>& chosen){
  counter++;
  if(chosen.size()>=ub){
    return;
  }
  if((*(universe.b)).none()){
    ub = chosen.size();
    return;
  }
  if(chosen.size()==ub-2){
    for(int i=0;i<sets.size();i++){
      if(sets[i].size() == universe.size()){
        chosen.push_back(sets[i].id);

        ub = chosen.size();
        chosen.pop_back();
        return;
      }
    }
  }
  sort(sets.begin(),sets.end(),set_sorter);
  remove_subsets(sets);
  int sum = 0;
  for(int i=0;i<ub-chosen.size()&&i<sets.size();i++){
    sum+= sets[i].size();
  }
  if(sum<universe.size()){
    return;
  }
  int bv = branch_value(universe,sets);
  if(bv==-2){
    return;
  }
    bitarray nu (universe);
    vector<bitarray> ns = deep_clone(sets);
  if(bv!=-1){
    chosen.push_back(sets[bv].id);
    remove_set(nu,ns,bv);
    bb(nu,ns,chosen);
    chosen.pop_back();
  }else{

    chosen.push_back(sets[0].id);
    remove_set(nu,ns,0);
    bb(nu,ns,chosen);
    chosen.pop_back();
    sets.erase(sets.begin());
    bb(universe,sets,chosen);
  }
}

int main (){
  int e;
  int n;
  scanf("%d",&e);
  scanf("%d",&n);

  vector<bitarray> s;
  
  for(int i=0;i<n;i++){
    int x;
    scanf("%d",&x);
    bitarray p (i);
    for(int j=0;j<x;j++){
      int t;
      scanf("%d",&t);
      (*(p.b)).set(t);
    }
    s.push_back(p);
  }

  bitarray universe (0);
  for(int i=0;i<n;i++){
    (*(universe.b))|=(*(s[i].b));
  }
  vector<int> chosen;
  ub = s.size();
  bb(universe,s,chosen);
  cout<<ub;
  cout<<endl;
  cout<<counter;
  cout<<endl;
  return 0;
}