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