时间限制:500MS 内存限制:1000K 提交次数:157 通过次数:62
题型: 编程题 语言: C++;C
Description
要成为ACM大牛,要掌握很多必需的知识点。某些知识点可以推导出别的知识点,所以在比赛中遇到的新问题,很多时候可以由你学过的知识中推导得到。现在给出要掌握的所有知识点数及知识点之间的推导关系。为了降低难度,假定知识的这种推导关系是单向的,即若A知识能直接(或间接)推导出B知识,那么B知识是无法直接(或间接)推导出A知识的。一个新手想尽快掌握所有知识点,他至少需要掌握多少知识呢?
输入格式
第一行0<n<=1000,0<m<n*n.。n表示必需掌握的知识点数目,编号0~n-1。m为知识点间推导关系总数。接下来m行,每行A B两个数,表示从A知识可以推导出B知识。
输出格式
一个数x,表示最少要掌握的知识数。
输入样例
8 4
0 1
0 2
1 3
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
/*这里用到了c++的sort函数,用c的qsort来排序也可以*/ /*大水题,第二个数都是被推导出来的,只要统计全部第二个数 ,这些就是不用学习的,总数n-count就是结果*/ #include<stdio.h> #include<algorithm> using namespace std; int main() { int a[100000],b[100000]; int i,n,m,count=0; scanf("%d%d",&n,&m); for(i=0; i<m; i++) scanf("%d%d",&a[i],&b[i]); sort(b,b+m);/*对数组b排序*/ for(i=0; i<m; i++)/*对已经排好的数组b求不同元素的个数 只需要某一个数不等于它的后一个数,count+1*/ if(b[i]!=b[i+1]) count++; printf("%d",n-count); }
1 4
输出样例
4
Time:15ms