记录编号	35688	评测结果	AAAAAAAAAA
题目名称	课程安排问题	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-02-28 18:58:28	内存使用	0.46 MiB

#include<fstream>
#include<algorithm>
using namespace std;
struct node {
	int s,next;
};
struct edge {
	int y,v,next,f;
};
int i,j,k,n,m,top,tmp,t,head,tail,min,sum=0,p,x,y;
edge e[101];
node a[101];
bool f[101];
bool q[101];
int queue[10000][5];
int ind[101];
int af[101];
void add(int x1,int y1,int v1)
{
	m++;
	a[x1].s=a[x1].s+1;
	e[m].y=y1;
	e[m].v=v1;
	e[m].next=a[x1].next;
	a[x1].next=m;
}
void swap(int x,int y)
{
	queue[0][1]=queue[x][1];
	queue[x][1]=queue[y][1];
	queue[y][1]=queue[0][1];
	queue[0][2]=queue[x][2];
	queue[x][2]=queue[y][2];
	queue[y][2]=queue[0][2];
}
int main()
{
	ifstream fin("curriculum.in");
	ofstream fout("curriculum.out");
	fin>>n;
	m=0;
	for (i=1;i<=n;i++)
		af[i]=0;
	for (i=1;i<=n;i++)
	{
		fin>>k;
		for (j=1;j<=k;j++)
		{
			fin>>y;
			x=i;
			add(y,x,1);
		}
	}
	for (i=1;i<=m;i++)
	{
		ind[e[i].y]++;
	}
	head=1;tail=0;
	for (i=1;i<=n;i++)
		f[i]=false;
	for (i=1;i<=n;i++)
		if (ind[i]==0)
		{
			sum++;
			af[i]=sum;
			tail++;
			queue[tail][1]=i;
			f[i]=true;
		}
	j=1;
	queue[1][2]=0;
	tmp=queue[head][1];
	sum=0;
	while (head<=tail)
    {
		int mini=100000000;
		int u;
		for (i=head;i<=tail;i++)
			if (queue[i][1]<mini)
			{
				mini=queue[i][1];
				u=i;
			}
		swap(head,u);
        tmp=queue[head][1];
		sum++;
		af[queue[head][1]]=sum;
        f[tmp]=true;
        t=a[tmp].next;
		for (i=1;i<=n;i++)
			q[i]=false;
        for (i=1;i<=a[tmp].s;i++)
          {
            ind[e[t].y]--;
            if (ind[e[t].y]==0)
			{
				q[e[t].y]=true;
                tail++;
                queue[tail][1]=e[t].y;
                queue[tail][2]=head;
                f[e[t].y]=true;
              };
            t=e[t].next;
          };
      head++;
    };
	i=0;
	bool t=true;
	for (i=1;i<=n;i++)
	{
		if (ind[i]!=0) t=false;
	}
	if (t)
	{
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			if (i==af[j])
				fout<<j<<' ';
		}
	}else
	{fout<<"no";}
	fin.close();
	fout.close();
	return 0;
}