比赛 |
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;
}