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/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )
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!