并查集
题目意思就是问每个集合元素与集合中第一个点合并,询问和0的祖宗节点相同的个数
暴力枚举下,看代码
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
int p[N];
int n, m;
inline int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
inline void solve()
{
while(cin >> n >> m, n || m)
{
for (int i = 0; i < n; i ++ ) p[i] = i;
while (m -- )
{
int k, x, y;
cin >> k >> x;
for (int i = 2; i <= k; i ++ )
{
cin >> y;
p[find(x)] = find(y);
}
}
int cnt = find(0), res = 0;
for (int i = 0; i < n; i ++ )
if (find(i) == cnt)
res ++;
cout << res << endl;
}
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}