まずは「ある集合のあつまりを選んだ時、その集合が問題文の条件を満たすか？」という判定問題を考えましょう。
判定問題は次の手順で解くことができます。

• はじめに整数の集合 \(T\) がある。\(T\) ははじめ空集合である。
• 選んだ集合を \(s_1, s_2, \dots, s_k\) とする。\(i=1, 2, \dots, k\) に対して次の操作を行う。
  • s_i に含まれている整数をすべて \(T\) に追加する。(\(T\) にすでに含まれている整数は新たに追加されない。)
• 上の操作を終了したときに \(T\) に \(1, 2, \dots, N\) がすべて含まれていれば答えは Yes, そうでなければ No である。

このアルゴリズムは \(T\) を C++ の std::set や Python の dict などの集合型を使って管理すると \(\mathrm{O}(N M \log N)\) 程度で動作します。よって、\(2^M-1\) 通り全ての選び方に対して判定問題を解けば元の問題を \(\mathrm{O}(2^M N M \log N)\) で計算することができます。

集合の選び方を 1 回ずつ全て調べる部分は bit 全探索 と呼ばれる手法で実装できます。
(以下では、集合が \(S_0, S_1, \dots, S_{M-1}\) と 0-indexed で番号づけられている場合を説明します。) bit 全探索とは、\(0\) 以上 \(2^M\) 未満の整数 \(x\) について、

• (\(x\) を 2 進表記したときの \(0\) bit 目が 1) \(\iff\) (集合 \(S_0\) を選ぶ)
• (\(x\) を 2 進表記したときの \(1\) bit 目が 1) \(\iff\) (集合 \(S_1\) を選ぶ)
• \(\vdots\)
• (\(x\) を 2 進表記したときの\(M-1\) bit 目が 1) \(\iff\) (集合 \(S_{M-1}\) を選ぶ)

というように \(x\) と集合の選び方を対応させて探索する手法です。(ここで \(i\) bit 目とは 2 進表記の \(2^i\) の桁のことをいいます。)
例えば \(M = 3, x = 3\) の場合、\(3\) を 2 進表記すると \(3 = 2^1 + 2^0\) で 011 になるので、\(S_0\) と \(S_1\) を選ぶのに対応します。

このような対応付けによって、全ての集合の選び方は \(0\) 以上 \(2^M\) 未満の整数と 1 対 1 で対応します。たとえば \(M=3\) について \(0\) 以上 \(2^3 = 8\) 未満の整数を 2 進表記で列挙すると次のようになります。

000
001
010
011
100
101
110
111

上の例を見ると、すべての選び方に対して、それに対応する整数が範囲内に存在すると分かります。(例えば 「\(S_0, S_2\) を選ぶ」という選び方に対応する整数は 2 進表記で 101 で、これは \(5\) と対応しています。)

このような対応付けを利用すれば \(0\) 以上 \(2^M\) 未満の整数を for loop で走査して、整数を集合に変換することで、全ての選び方を重複なく調べることができます。また、整数 \(x\) の \(i\) bit 目は右シフトや論理積などの bit 演算を利用して (x >> i) & 1 になるため、整数から集合への変換もただちに行えます。

以上に説明した bit 全探索によってこの問題を \(\mathrm{O}(2^M N M \log N)\) で解くことができて、これは十分高速です。

• 実装例(C++)

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> a(M);
  for (int i = 0; i < M; i++) {
    int c;
    cin >> c;
    a[i].resize(c);
    for (auto& x : a[i]) cin >> x;
  }
  int ans = 0;
  for (int b = 0; b < (1 << M); b++) {
    set<int> s;
    for (int i = 0; i < M; i++) {
      if ((b >> i) & 1) {
        for (auto& x : a[i]) s.insert(x);
      }
    }
    ans += (int)s.size() == N;
  }
  cout << ans << "\n";
}