POJ 2367 Genealogical tree【拓扑排序】

浏览数：21 / 时间：2015年06月08日

题意：大概意思是--有一个家族聚集在一起，现在由家族里面的人讲话，辈分高的人先讲话。现在给出n，然后再给出n行数第i行输入的数表示的意思是第i行的子孙是哪些数，然后这些数排在i的后面。

比如样例 5

4 5 1 0

1 0

5 3 0

3 0

1后面没有数

2后面有4 5 1

3后面有1

4后面有5 3

5后面有3

技术分享

拓扑排序的一点小体会

（1）先把图储存下来，然后储存相应顶点的度数

（2）在图中选择没有前驱的点（即入度为0的点），加入队列中

（3）将以这一点为起点的边删去（将这一点指向的点的入度减1）

（4）重复上面的操作，直到没有入度为0的点

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;
int iq,n;
int queue[1000],map[1000][1000],indegree[1000];

void toposort()
{
	int i,j,k;
	iq=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(map[i][j])
			indegree[j]++;			
		}
	}
	
	for(i=1;i<=n;i++)
	{
			for(j=1;j<=n;j++)
		{
			if(indegree[j]==0)
			{
				queue[iq++]=j;
				break;
			}
		}
		indegree[j]=-1;//把这一点加进去以后，将这一点的入度记为-1，以免下次又将它加进队列 
		for(k=1;k<=n;k++)
		{
			if(map[j][k])
			indegree[k]--;
		}		
	}	
}	

int main()
{
	int i,v;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		while(scanf("%d",&v)!=EOF&&v)
		map[i][v]=1;		
	}
	toposort();
	for(i=0;i<iq-1;i++)
	printf("%d ",queue[i]);
	printf("%d",queue[i]);	
}

拓扑排序的第一题--@_@

go--go

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

POJ 2367 Genealogical tree【拓扑排序】