admin 管理员组

文章数量: 1184232

原题链接

题目大意

有 n ( 2 ≤ n ≤ 200 ) n(2\le n\le 200) n ( 2 ≤ n ≤ 2 0 0 ) 个人要拷贝光盘，每个人都可以给自己愿意给的人进行再次拷贝。求最少要将光盘给多少人拷贝。

解题思路

实际上，本题就是求联通块的个数。很明显，要使用 d f s dfs d f s ，但是，如何求最少？肯定是将联通块的顶点进行一次遍历，从最大的联通块到小的联通块，并且每遇到一个没有被标记的点，就将答案加一。那么如何将连通块的顶点排序？那就要使用 拓扑排序 了。
按照拓扑排序的原理，是将入度为0的点先放入队列，再将与其相连的点入度减一，再次放入此时入度为0的点：

代码实现 

#include<iostream>#include<map>#include<cstring>#include<vector>#include<stack>usingnamespace std;
vector<int> Map[210];int n,t,ans;
stack<int> o;bool v[210];voiddfs1(int n2)//进行拓扑排序{
	v[n2]=true;for(int i=0;i<Map[n2].size();i++)//遍历临界列表if(!v[Map[n2][i]])//判重dfs1(Map[n2][i]);
	o.push(n2);return;}voiddfs2(int n2)//进行扩展{
	v[n2]=true;for(int i=0;i<Map[n2].size();i++)//遍历临界列表if(!v[Map[n2][i]])//判重dfs2(Map[n2][i]);return;}intmain(){
	cin>>n;for(int i=1;i<=n;i++){while(true){
			cin>>t;if(t==0)break;
			Map[i].push_back(t);//记录有向图}}for(int i=1;i<=n;i++)//拓扑排序if(!v[i])dfs1(i);memset(v,0,sizeof(v));for(int i=1;i<=n;i++){int now=o.top();//使用栈存储拓扑排序结果
		o.pop();if(!v[now]){dfs2(now);
			ans++;}}
	cout<<ans;}

样例

输入 

523404500010

输出 

1

本文标签： 拓扑排序 编程 的点

版权声明：本文标题：刻录光盘最少人数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1774381712a3571090.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。