10305 – Ordering Tasks
John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.
Input
The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 <= n <= 100 andm. n is the number of tasks (numbered from 1 to n)
and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed
before task j. An instance with n = m = 0will finish the input.
Output
For each instance, print a line with n integers representing the tasks in a possible order of execution.
Sample Input
Sample Output
裸的，输出顺序任意，所以DFS做法可以求得。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int maxn=110;
int mp[maxn][maxn];
int toposort[maxn];
int vis[maxn];
int n,m,cnt;
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=n;i++)
if(!vis[i]&&mp[x][i]&&i!=x) dfs(i);
toposort[cnt++]=x;
}
void solve()
{
CLEAR(vis,0);
for(int i=1;i<=n;i++)
if(!vis[i]) dfs(i);
}
int main()
{
int x,y;
std::ios::sync_with_stdio(false);
while(cin>>n>>m&&(n+m))
{
CLEAR(mp,0);
while(m–)
{
cin>>x>>y;
mp[x][y]=1;
}
cnt=0;
solve();
for(int i=cnt⑴;i>=0;i–)
printf(i==0?"%d
":"%d ",toposort[i]);
}
return 0;
}
HDU 1285
肯定比赛名次
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13115 Accepted Submission(s): 5264
其他说明：符合条件的排名可能不是唯1的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保1定能有1个符合要求的排名。
波比源码 » 图论：拓扑排序
