做电脑图标的网站,如何做下载网站,货运配载做网站,住建网查询舞会邀请
CODE[VS] 2604
题目大意#xff1a;
Smart要叫一些人开Party#xff0c;每个人可以通知一部分人#xff0c;Smart去通知一些人#xff0c;再让这些人去通知其他人#xff0c;问Smart最少通知几个人#xff0c;可以使全部人都被通知到
原题#xff1a;
题目…舞会邀请
CODE[VS] 2604
题目大意
Smart要叫一些人开Party每个人可以通知一部分人Smart去通知一些人再让这些人去通知其他人问Smart最少通知几个人可以使全部人都被通知到
原题
题目描述 Description
Smart是一位颇有成就的艺术家他因油画作品《我爱北京天安门》闻名于世界。现在他为了报答帮助他的同行们准备开一个舞会。 Smart准备邀请n个已经确定的人可是问题来了 这n个人每一个人都有一个小花名册名册里面写着他能够通知到的人的名字。比如说在A的人名单里写了B那么表示A能够通知到B但是B的名单里不见得有A也就是说B不见得能够通知到A。 Smart觉得需要确定自己需要通知到多少个人人数m能够实际将所有n个人都通知到。并求出一种方案以确定m的最小值是多少。 注意自己的名单里面不会有自己的名字。
输入描述 Input Description
第一行一个数n1≤n≤200。接下来n行第i1行表示编号为i的人的小花名册名单名单以0结束。
输出描述 Output Description
一个整数即m的值。
样例输入 Sample Input
5 1
2 0
1 3 0
0
0
1 0样例输出 Sample Output
2数据范围及提示 Data Size Hint
1≤n≤200
题目大意
将图中的强连通分量找出来然后将其所谓一个点然后再找入读为0的点的个数通知即可
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,m,x,ans,b[205],rd[205],a[205][205];
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,x);while (x){a[i][x]1;//读入scanf(%d,x);}}for (int k1;kn;k)for (int i1;in;i)for (int j1;jn;j)a[i][j]max(a[i][j],min(a[i][k],a[k][j]));//Floyedfor (int i1;in;i)if (!b[i])//判断是否已经被缩了{b[i]m;//缩点for (int ji1;jn;j)if (a[i][j]a[j][i])//强连通b[j]m;//记录}for (int i1;in;i)for (int j1;jn;j)if (a[i][j]b[i]!b[j])//链接并不是同一个点rd[b[j]]1;//有入读for (int i1;im;i)if (!rd[i]) ans;//入读为0printf(%d,ans);
}
