[각종 면접 문제] 미 션 스케줄 링. - 탁본 정렬.

n 개의 임 무 를 완성 해 야 합 니 다 (번호 1 에서 n). 임무 간 에 의존 관계 가 있 습 니 다. 만약 에 임무 a 가 임무 b 와 c 에 의존 하면 임무 b 와 임무 c 가 완성 한 후에 야 임 무 를 완성 할 수 있 습 니 다.모든 의존 관 계 를 정 하여 이 임무 들 이 완 성 될 수 있 는 지 여 부 를 판단 한다.만약 완성 할 수 있다 면 합 법 적 인 임무 완성 서열 을 제시 하 십시오.
샘플: 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;
}