求助一道站外题
  • 板块灌水区
  • 楼主FormulaOne
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/8/17 09:04
  • 上次更新2023/11/4 10:23:51
查看原帖
求助一道站外题
180406
FormulaOne楼主2021/8/17 09:04

总所周知,大佬喜欢和大佬交流和组队。已知有多个讨论小组,我们认为如果这个讨论小组里有一个人可能是大佬,那么这个小组所有成员都可能是大佬。我们已经知道第0号同学是大佬,请你帮忙数数有多少人可能是大佬。

注:如果0号同学所在的小组里有1号同学,那么1号同学可能是大佬,1号同学所在的小组里的人也都有可能是大佬,以此类推。

Input 输入文件包含多组数据。

对于每组测试数据: 第一行为两个整数n和m, 其中n是学生的数量, m是讨论小组的数量。 接下来m行,每一行有一个整数k,代表讨论小组中学生的数量。之后,有k个整数代表这个小组里每个 学生的编号(在0到n-1之间)。 n = m = 0表示输入结束,不需要处理。

0 < n ≤30000,0 ≤ m ≤ 500。

Output 对于每组输入,输出一行一个整数表示可能是大佬的人的数量

Sample Input 100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0

Sample Output 4 1 1 代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,a[30001][501],b[501][30001],k[30001],len[30001],c[30001],ans;
int main()
{
	while(true)
	{
		memset(c,0,sizeof(c));
		memset(len,0,sizeof(len));
		ans=0;
		scanf("%d%d",&n,&m);
		if(n==0&&m==0) break;
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&k[i]);
			for(int j=1;j<=k[i];j++)
			{
				scanf("%d",&b[i][j]);
				a[b[i][j]][++len[b[i][j]]]=i;
			}
		}
		c[0]=1;
		for(int i=0;i<n;i++)
			if(c[i]==1)
			{
				for(int j=1;j<=len[i];j++)
					for(int l=1;l<=k[a[i][j]];l++)
						c[b[a[i][j]][l]]=1;
			}
//		for(int i=0;i<n;i++)
//			if(c[i]==1)
//			{
///				for(int j=1;j<=len[i];j++)
//					for(int l=1;l<=k[a[i][j]];l++)
//						c[b[a[i][j]][l]]=1;
//			}
		for(int i=0;i<n;i++)
			if(c[i]==1)
				ans++;
		printf("%d\n",ans);				
	}
	return 0;
}
2021/8/17 09:04
加载中...