https://vjudge.net/problem/UVA-10305
题目
想完成某些任务就要先完成这个任务的前提任务(啥)
把这种关系画成图就知道了
想完成3就必须先完成1和2
我们可以按 1 2 3 5 4的顺序来完成任务
输入一些任务的关系,求一种可能完成任务的方法
题解
这种问题叫拓扑排序……
解决方法很简单,就是只做现在就能做的任务(没有前提的)
因为现在能做的任务可能不止一个,那么解也可能有多个
还可以把反过来想,最后做不是其他任务前提的任务……
如果形成了环,那么就不可能完成这些任务
那么可以用DFS,最先使用最深的节点(这都是啥),如果发现回边就说明有环,排序失败
题目没说判断回边,就不管了
AC代码
#include<bits/stdc++.h> using namespace std; #define REP(i,x,y) for(register int i=(x); i<(y); i++) #define REPE(i,x,y) for(register int i=(x); i<=(y); i++) #ifdef LOCAL #define DBG(a,...) printf(a, ##__VA_ARGS__) #else #define DBG(a,...) (void)0 #endif int E[101][101]; int S[101]; int n,m; enum vtype{DISCOVERED=1, UNDISCOVERED=0, VISITED=-1}; int ans[101], ansi=101; inline bool solve(int k) { S[k]=DISCOVERED; REPE(i,1,n) { if(E[k][i]) { if(S[i]==DISCOVERED) return false; if(S[i]==UNDISCOVERED && !solve(i)) return false; } } S[k]=VISITED; ans[--ansi]=k; return true; } int main() { while(~scanf("%d%d", &n, &m) && n) { memset(E,0,sizeof E); memset(S,0,sizeof S); ansi=101; int i,j; while(0<m--) { scanf("%d%d", &i, &j); E[i][j]=1; } REPE(i,1,n) { if(!S[i]) { if(!solve(i)); //{wa=true; break;} } } // if(wa) if(ansi<101) printf("%d", ans[ansi]); REP(i,ansi+1,101) { printf(" %d", ans[i]); } putchar(' '); } return 0; }