比赛 20120224 评测结果 AAAAAAAAAW
题目名称 课程安排问题 最终得分 90
用户昵称 QhelDIV 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-02-24 19:51:53
显示代码纯文本
#include <fstream>
using namespace std;
ifstream fin("curriculum.in");
ofstream fout("curriculum.out");
const int NodeNumber=100000;
int V,E,d[NodeNumber],f[NodeNumber],Time,Ans[NodeNumber],AN;
int m[1002];
bool Ifvisited[NodeNumber],flag=true;
class AbMap
{
public:
	int Data,Name;
	AbMap *Xt;
}Map[NodeNumber],*last[NodeNumber];
void Add(int N1,int N2,int Dis)
{
	last[N1]->Data=Dis;
	last[N1]->Name=N2;
	last[N1]->Xt=new AbMap;
	last[N1]=last[N1]->Xt;
	last[N1]->Xt=0;
}
void Initialize()
{
int i,j,St,En;
	fin>>V;
	for(i=1;i<=V;i++)
		last[i]=&Map[i];
	for(i=1;i<=V;i++)
	{
		fin>>m[i];
		for(j=1;j<=m[i];j++)
		{
			fin>>En;
			Add(i,En,1);
		}
	}
}

void DFS(int pos)
{
AbMap *Pt;
	d[pos]=++Time;
	for(Pt=&Map[pos];Pt->Xt;Pt=Pt->Xt)
		if(!Ifvisited[Pt->Name])
		{
			Ifvisited[Pt->Name]=true;
			DFS(Pt->Name);
		}
		else
			if(d[Pt->Name]>=d[pos] && f[Pt->Name]<=f[pos])
			{
				flag=false;
				return ;
			}
	if(flag==false)
		return ;
	f[pos]=++Time;
	Ans[++AN]=pos;
}

void Topological()
{
int i;	
	for(i=1;i<=V;i++)
		if(!Ifvisited[i])
		{
			Ifvisited[i]=true;
			DFS(i);
		}
}

void Op()
{
int i;
	if(flag)
		for(i=1;i<=AN;i++)
			fout<<Ans[i]<<" ";
	else
		fout<<"NO";
	fout<<endl;
}

int main()
{
	Initialize();
	
	Topological();
	
	Op();
	
	fin.close();
	fout.close();
	return 0;
}