首页 > 代码库 > 大牛之路II
大牛之路II
时间限制:500MS 内存限制:1000K 提交次数:138 通过次数:31
题型: 编程题 语言: C++;C
Description
要成为ACM大牛，要掌握很多必需的知识点。某些知识点可以推导出别的知识点，所以在比赛中遇到的新问题，很多时候可以由你学过的知识中推导得到。现在给出要掌握的所有知识点数及知识点之间的推导关系。注意，若A知识可以直接（间接）推导出B知识，B知识也是有可能直接（间接）推导出A知识的。一个新手想尽快具有解决所有知识点的能力，他至少需要掌握多少知识呢？
输入格式
多组数据，每组数据格式为：第一行1<=n<=18,0<=m<=n*n.。n表示必需掌握的知识点数目，编号0~n-1。m为知识点间推导关系总数。接下来m行，每行A B两个数，表示从A知识可以推导出B知识。当n==0 && m==0时，结束程序。两个Case间有一空行。
输出格式
一个数x，表示最少要掌握的知识数。
输入样例
8 40 10 21 31 42 20 11 00 0
输出样例
41
这里简述flag数组的作用，先把flag所有元素初始化为0，在这题中
3 2
0 1
0 2
这类例子的结果应该是2（即0 2 都应该学） flag作为哨兵，每计算过后把结果改为1，下次遇到直接跳过
#include<cstdio>#include<cstring>int pre[1000];int flag[20];int find(int x){ return pre[x]==x?x:(pre[x]=find(pre[x]));}int main(){ int i,n,m; while(1) { scanf("%d%d",&n,&m); memset(flag,0,sizeof(flag)); if(!n&&!m) break; for(i=0;i<n;i++) pre[i]=i; int a,b,total; total=n; for(i=0;i<m;i++) { scanf("%d%d",&a,&b); if(flag[b]) continue; a=find(a); b=find(b); flag[b]=1; if(a!=b) {pre[a]=b;total--;} } printf("%d\n",total); } return 0;}
大牛之路II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。