学步园

题目链接：xmu1073

方法：拓扑排序

代码：

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int MAXNUM=505;//最大顶点数目 
typedef string type;
struct node
{
	type data;
	vector <int> next;//存储该顶点可以访问的顶点序号 
};
struct graph
{
	node vex[MAXNUM];//顶点信息 
	int vexnum,degree[MAXNUM];//顶点数目，顶点入度 
};
bool topsort(graph g)
{
	stack <int> s;
	int i,j,count=0,flag=1;
	int ans[MAXNUM];//记录拓扑排序后顶点的序号 
	for(i=0;i<g.vexnum;i++)
		if(!g.degree[i])s.push(i);
	while(!s.empty())
	{
		int tmp=s.top();s.pop();
		ans[count]=tmp; count++;
		for(i=0;i<g.vex[tmp].next.size();i++)
			if(!(--g.degree[g.vex[tmp].next[i]]))
				s.push(g.vex[tmp].next[i]);
	}
	if(count<g.vexnum)
	{
		cout<<"Impossible!"<<endl;
		return false;
	}
	else  
	{	for(i=0;i<g.vexnum;i++)
			if(i<g.vexnum-1)cout<<g.vex[ans[i]].data<<' ';
			else cout<<g.vex[ans[i]].data<<endl;
		return true;
	}
}
int main()
{
	int  n,m;
	while(cin>>n)
	{
		int i,j;
		graph g; g.vexnum=n;
		for(i=0;i<n;i++)cin>>g.vex[i].data;
		memset(g.degree,0,sizeof(g.degree));
		for(i=0;i<n;i++)
		{
			cin>>g.degree[i];
			for(j=0;j<g.degree[i];j++)
			{
				int tmp;
				cin>>tmp;tmp=tmp-1;//序号从0开始 
				g.vex[tmp].next.push_back(i);
				//由于是先修课程，应该是前面的课程可以访问该节点 
			}
		}
		bool res=topsort(g);
		/*if(res)cout<<"拓扑排序成功"<<endl;
		else cout<<"图中存在有环路"<<endl;*/
	}
	return 0;
}