bit全探索 で時間計算量 \(O(2^N M)\) あるいは \(O(2^NKM)\) でこの問題に正解できますが、 \(M\) が大きくても対応できる解法を示します。
なお、以降の解説は bit 全探索への理解を前提とします。

集合 \(S_i\) の補集合、つまり集合 \(S_i\) に含まれない要素の集まりを \(\overline{S_i}\) と表記します。
例えば、 \(8\) 台のマシンがある中でマシン \(1,2,4,6\) の補集合はマシン \(3,5,7,8\) です。
bit 演算では、 s の補集合は s^((1<<N)-1) で計算できます。

• \(R_i = 0\) なる情報は、以下の通りに変換されます。
  • 感染したマシンとしてありうるのは、 \(\overline{S_i}\) の部分集合です。これを「生きる」情報と呼びます。
• \(R_i = 1\) なる情報は、以下の通りに変換されます。
  • \(S_i\) 中の少なくとも \(1\) 台は感染しているべきなので、 \(\overline{S_i}\) の部分集合だけが感染しているということはありません。これを「死ぬ」情報と呼びます。

ひとまず集合 \(X\) に対して情報を記録して、その後に \(X\) の部分集合に伝播させるということをまとめて行いたいです。
これは、 高速ゼータ変換 で実現できます。

• 高速ゼータ変換について
• 高速ゼータ変換／高速メビウス変換

感染しているマシンの集合としてありうるのは、「生きる」情報を全て受け取っており、かつ「死ぬ」情報をひとつも受け取っていないもので、それらに限られます。

時間計算量 \(O(2^NN + KM)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> f(M,0),R(M);

  int dc=0;
  vector<int> dead(1<<N,0);
  int ac=0;
  vector<int> alive(1<<N,0);

  for(int i=0;i<M;i++){
    int K;
    cin >> K;
    for(int j=0;j<K;j++){
      int S;
      cin >> S;
      f[i]|=(1<<(S-1));
    }
    cin >> R[i];

    if(R[i]==0){
      ac++;
      alive[f[i]^((1<<N)-1)]++;
    }
    else{
      dc++;
      dead[f[i]^((1<<N)-1)]++;
    }
  }

  for(int k=0;k<N;k++){
    for(int i=0;i<(1<<N);i++){
      if(i&(1<<k)){
        alive[i^(1<<k)]+=alive[i];
        dead[i^(1<<k)]+=dead[i];
      }
    }
  }

  int res=1e9;
  for(int i=0;i<(1<<N);i++){
    if(alive[i]==ac && dead[i]==0){
      res=min(res,__builtin_popcount(i));
    }
  }
  cout << res << "\n";
  return 0;
}