有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。
样例：
n=5
1->2,3
3->4
上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5
读完题就发现是个拓扑排序，直接上模板吧！但是注意it=map.find()之后有可能为空的，直接connect=it->second就报错了。
typedef int JobID;
/*
* deps[id]表示任务id所依赖的任务
* 如果存在合法的任务完成序列，返回true，否则返回false
* 合法的任务序列请存放在参数result中（已经分配空间，不需要push_back）
*/
bool dfs(int u,const map<JobID,vector<JobID> >& deps,vector<JobID>& result,int& tail,vector<JobID>& vis);
bool jobSchedule(const map<JobID, vector<JobID> > &deps, int n,
vector<JobID> &result) {
int tail=0;
vector<JobID> vis(n+1,0);
for(int i=1;i<=n;i++)
if (vis[i]==0&&!dfs(i,deps,result,tail,vis) )
return false;
return true;
}
bool dfs(int u,const map<JobID,vector<JobID> >& deps,vector<JobID>& result,int& tail,vector<JobID>& vis)
{
vis[u]=-1;
map<JobID,vector<JobID> >::const_iterator it = deps.find(u);
if ( it !=deps.end() )
{
const vector<JobID>& connect=it->second;
for(int i=0;i<connect.size();i++)
{
int v=connect[i];
if ( vis[v]==1 )
continue;
else if ( vis[v]==-1 )
return false;
else if ( !dfs(v,deps,result,tail,vis) )
return false;
}
}
vis[u]=1;
result[tail++]=u;
return true;
}