1人が同じ曲を複数回選ぶことはないため、「全員に選ばれた」は「\(N\) 回選ばれた」と同値です。よって、各曲が選ばれた回数を記録することで答えを求めることができます。

計算量は \(O(N+M+\sum K_i)\) になります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int>cnt(m+1);
  for(int i=0; i<n; i++){
    int k;
    cin >> k;
    for(int j=0; j<k; j++){
      int c;
      cin >> c;
      cnt[c]++;
    }
  }

  int ans = 0;
  for(int i=1; i<=m; i++){
    if(cnt[i] == n){
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M = map(int, input().split())
cnt = [0] * (M+1)
for _ in range(N):
  K, *C = map(int, input().split())
  for c in C:
    cnt[c] += 1

ans = 0
for v in cnt:
  if v == N:
    ans += 1
print(ans)

なお、python には set の積集合を求める演算子が存在するため、これを用いることでも問題を解くことができます。

実装例 (Python)

N, M = map(int, input().split())
cnt = [0] * (M+1)
ans = set(range(1, M+1))
for _ in range(N):
  K, *C = map(int, input().split())
  ans &= set(C)

print(len(ans))