LiveArchive-2432, UVa-1119, SPOJ-PFDEP : Project File Dependencies

問題概要

N(<100)個のファイル間の依存関係が与えられるので、どのプロジェクトから開始すべきか順に出力する問題。複数ある場合は辞書順最小を返す。

解法

トポロジカルソートするだけ。辞書順最小とかはあらかじめ降順にソートしておけば良い。

acceptされたコード

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 100;

vector<int> graph[MAX_N];
int N;
int order[MAX_N];
bool visited[MAX_N];

void dfs(int v, int& p){
	visited[v] = true;
	for(int i=0; i<(int)graph[v].size(); i++){
		int u = graph[v][i];
		if(!visited[u]){
			dfs(u, p);
		}
	}

	order[p--] = v;
}

void init(){
	int M;
	scanf("%d%d",&N, &M);

	//初期化
	for(int i=0; i<N; i++){
		graph[i].clear();
	}
	memset(visited, false, sizeof(visited));

	for(int i=0; i<M; i++){
		int tar, K;
		scanf("%d%d", &tar, &K);
		tar--;
		for(int j=0; j<K; j++){
			int x;
			scanf("%d", &x);
			x--;
			graph[x].push_back(tar);
		}
	}

	for(int i=0; i<N; i++){
		sort(graph[i].rbegin(), graph[i].rend());
	}
}

void solve(){
	int p = N-1;
	for(int i=N-1; i>=0; i--)if(!visited[i]){
		dfs(i, p);
	}

	for(int i=0; i<N; i++){
		printf("%d%c", order[i]+1, i==N-1?'\n':' ');
	}
}


int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		solve();
		if(T){
			puts("");
		}
	}
	return 0;
}