POJ 2367 Genealogical tree【拓扑排序】

题意：大概意思是--有一个家族聚集在一起，现在由家族里面的人讲话，辈分高的人先讲话。现在给出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【拓扑排序】

最新文章

热门文章