此题会出现以下两种情况
第一种: 如样例
5 2 4 3 0 4 5 0 0 0 1 0
这种情况只用教一个人(教1||2||5)就可以使是所有人都学会
第二种情况
5 3 0 4 0 5 0 5 0 0
这种情况必须要教1和2
解题思路:
通过观察第一种情况每个人都有人教所以小明挑一个人教就好了;第二种情况是有些人没有人教所以小明要把没有人教的人都教会了。
AC代码:
#includeusing namespace std; queueq; int n; int d[10000005]; int f[10000005]; int flag[10000005]; int hx[1000005]; int find(int x) { if(f[x]!=x) { return f[x]=find(f[x]); } return x; } void marger(int x,int y) { int a=find(x); int b=find(y); if(a!=b) { f[b]=f[a]; } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { f[i]=i; } for(int i=1;i<=n;i++) { for(int j=0;j<=n;j++) { int x; scanf("%d",&x); d[x]++;//表示x有人教 if(x==0) { break; } marger(i,x);//合并在一个集合中 } } int ans=0; for(int i=1;i<=n;i++) { if(find(i)==i) { ans++;//每个集合都至少教一个人 } } for(int i=1;i<=n;i++) { if(d[i]==0)//若发现有人没有人愿意教 { ans++;//这个人要被小明教 if(hx[find(i)]==0)//如果这个人是至少要被小明教的那个就保持原样 { ans--; hx[find(i)]=1; } } } printf("%d",ans); return 0; }
0.0分
0 人评分
C语言训练-最大数问题 (C语言代码)浏览:633 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:900 |
用筛法求之N内的素数。 (C语言代码)浏览:1260 |
WU-输出九九乘法表 (C++代码)浏览:1671 |
简单的a+b (C语言代码)浏览:606 |
P1000 (C语言代码)浏览:877 |
数字游戏 (C++代码)浏览:1185 |
程序员的表白 (C语言代码)浏览:598 |
字符串比较 (C语言代码)浏览:685 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:999 |