刻录光盘

题目

在PJOI2010夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？

组委会把这个难题交给了DYJ，DYJ分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人呢拿到光盘以后，其他人可以拿着U盘之类的东西去拷贝啊！

可是DYJ调查后发现，有些营员并不是那么合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们PJOI宣扬的团队合作精神格格不入！

现在假设总共有N个营员（2<=N<=200）,每个营员的编号为1~N。DJY给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B、C也会获得资料。

现在请你编写一个程序，根据回收上来的调查表，帮助DZY计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

输入

先是一个数N，接下来N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第N+1行表示第i个营员愿意把资料拷贝给那些营员编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。

输出

一个正整数，表示最少要刻录的光盘数。

输入样例

52 4 3 04 5 0001 0

输出样例

思路

这道题就是要求有向图的强连通分量，我们这里要用到Kosaraju算法。

Kosaraju算法大概是这样的：

第一次对图进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序。

把图转置，建成一个新的图。（转置就是将一个图上所有的有向边反向，本是x->y的一条边，转置后变为y->x）

按照退出顺序的逆序对反图进行第二次DFS遍历。

每次遍历得到的那些点即属于同一个强连通分量。

代码

#include
   
    #include
    
     using namespace std;int n,x,f[201],sum,ans;bool a[201][201],b[201][201],in[201];void dfs1(int e){
   	in[e]=1;	for (int i=1;i<=n;i++)	if (a[e][i]&&!in[i]) dfs1(i);	f[++sum]=e;}void dfs2(int e){
   	in[e]=1;	for (int i=1;i<=n;i++)	if (a[e][i]&&!in[i]) dfs2(i);}int main(){
   	scanf("%d",&n);//读入	for (int i=1;i<=n;i++)	{
   		scanf("%d",&x);//读入		while (x!=0)		{
   			a[i][x]=1;//建邻接矩阵			scanf("%d",&x);//读入		}	}	for (int i=1;i<=n;i++)	if (!in[i]) dfs1(i);//第一次对图进行dfs	for (int i=1;i<=n;i++)	for (int j=1;j<=n;j++)	if (a[i][j]) b[j][i]=1;//把图转置	memset(in,0,sizeof(in));//把访问记录清除	for (int i=n;i>=1;i--)	if (!in[f[i]])	{
   		ans++;//求出遍历的次数		dfs2(f[i]);//第二次对图进行dfs	}	printf("%d",ans);//输出	return 0;}

转载地址：http://pyth.baihongyu.com/

你可能感兴趣的文章