2014年3月8日 星期六

UVa OJ - 10305 Ordering Tasks

The following program is my ACcepted code for UVA-10305.
It's a for everybody to learn and discuss.
If there is any mistake or comment, please let me know.  :D

此乃UVA 10305 的AC code!
歡迎一同討論學習,如有錯誤與任何建議請留言 : )

//This program is for UVA 10305 Ordering Tasks
//題目來源 Problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1246

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 101
using namespace std;

bool map[MAX][MAX];
bool visit[MAX];
int ans[MAX], count;

void initial()
{
    memset(map, false, sizeof(map));
    memset(visit, false, sizeof(visit));
    memset(ans, 0, sizeof(ans));
}

void DFS(int p, int n)
{
    if(visit[p])
        return;
 
    visit[p] = true;
    for(int i = 1; i <= n; i++)
    {
        if(map[p][i])//there's path from p to i
            DFS(i, n);
    }
    ans[count--] = p;
    return;
}

int main()
{
    int n, m;  
     
    while(scanf("%d %d", &n, &m) != EOF)
    {
        if(n == 0 && m == 0)
            break;
     
        initial();
     
        while(m--)
        {
            int str, end;
            //there is a path from str to end
            scanf("%d %d", &str, &end);
            map[str][end] = true;
        }
     
        count = n;
        for(int i = 1; i <= n; i++)
            DFS(i, n);
     
        for(int i = 1; i < n; i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
    return 0;
}


Please feel free to use it after adding this blog as an reference. (http://autekroy.blogspot.tw) If there is any mistake or comment, please let me know. :D 

歡迎使用與分享任何內容,但請記得標示此部落格為出處。(http://autekroy.blogspot.tw/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )

沒有留言:

張貼留言

請留下您的任何想法或建議!
Please leave any thought or comment!