刻录光盘最少人数

原题链接

题目大意

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

解题思路

实际上，本题就是求联通块的个数。很明显，要使用 $dfs$ ，但是，如何求最少？肯定是将联通块的顶点进行一次遍历，从最大的联通块到小的联通块，并且每遇到一个没有被标记的点，就将答案加一。那么如何将连通块的顶点排序？那就要使用 拓扑排序 了。
按照拓扑排序的原理，是将入度为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