UVA 10305 Ordering Tasks 解题报告

题意：给定你n项工作，m个依赖关系（某件工作必须在另一件工作之前）,求出一个满足条件的序列

解题思路：深搜，假如x必须在y之前，那么map【y】【x】 = 1；先把没有前提的工作进入序列，然后遍历工作，如果一个工作没有进入序列那么深搜map 。。。

解题代码：

// File Name: uva10305.c
// Author: darkdream
// Created Time: 2013年06月15日 星期六 17时27分55秒

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
int map[105][105];
int canvisit[105];
int visit[105];
int ans[105] ;
int j ,n;
void dfs(int k )
{ 
    for(int i =  1;i <= n;i ++)
    {
      if(map[k][i] == 1 && !visit[i])
          dfs(i);
    }
        j ++;
    ans[j] = k;
    visit[k] = 1;

}
int main(){

   //freopen("/home/plac/problem/input.txt","r",stdin);
   //freopen("/home/plac/problem/output.txt","w",stdout);
   int m ;
   while(scanf("%d %d",&n,&m) != EOF)
   {

     if(n == 0 )
         break;
     memset(map,0,sizeof(map));
     memset(visit,0,sizeof(visit));
     memset(canvisit,0,sizeof(canvisit));
     memset(ans,0,sizeof(ans));
     int a, b;
     for(int i =1 ;i <= m;i ++)
     {
        scanf("%d %d",&a,&b);
        map[b][a] = 1;
        canvisit[b] = 1;
     }
     j = 0 ;
     for(int i =1 ;i <= n;i ++)
     {
       if(canvisit[i] == 0 )
       {
         visit[i] = 1;
         j ++;
         ans[j] = i;
       }
     }
     for(int i =1 ;i <= n;i ++)
     {
        if(!visit[i])
          dfs(i);
     }
     for(int i =1; i <= j;i ++)
       printf("%d ",ans[i]);
     printf("\n");
   }
return 0 ;
}