위상정렬을 이용해서 제가 문제를 풀었는데 계속 WA가 나와서 답답해서 질문 올립니당...
문제에 있는 예제도 해보고, 제가 나름대로 작성한 테스트 문제도 만들어서 작성해봤지만 계속 WA나오네요
제가 작성한 소스 올립니다.. 허접하지만 누가 문제점좀 찾아내 주세요 ㅠ.ㅠ
#include
#include
#define WHITE 5
#define GRAY 6
#define BLACK 7
#define CHECKED 3
#define UNCHECKED 4
#define TRUE 1
#define FALSE 0
#define MAX 1000000
int time;
typedef struct node {
char job;
int color;
int d;
int f;
node *pre;
node *next;
node *t_next;
} node;
void make_graph(node *head, char num1, char num2)
{
node *t, *r, *temp;
temp = (node *)malloc(sizeof(node));
temp->job = num2;
temp->color = WHITE;
temp->d = MAX;
temp->f = MAX;
temp->pre = NULL;
temp->next = NULL;
if(head[num1].next == NULL)
head[num1].next = temp;
else {
t = head[num1].next;
r = &head[num1];
while((t != NULL) && (t->job < num2)) {
r = t;
t = t->next;
}
r->next = temp;
temp->next = t;
}
}
void DFS_VISIT(node *head, node **thead, int i)
{
node *temp;
head[i].color = GRAY;
time = time + 1;
head[i].d = time;
temp = &head[i];
while(temp->next != NULL) {
temp = temp->next;
if(head[temp->job].color == WHITE) {
head[temp->job].pre = &head[i];
DFS_VISIT(head, thead, temp->job);
}
}
head[i].color = BLACK;
time = time + 1;
head[i].f = time;
head[i].t_next = *thead;
*thead = &head[i];
}
void DFS(node *head, node **thead, int number_of_vertex)
{
int i;
time = 0;
for(i=number_of_vertex; i>0; i--) {
if(head[i-1].color == WHITE) {
DFS_VISIT(head, thead, i-1);
}
}
}
int main()
{
char job[100];
int T, N, M, i, j;
node *head, *thead, *t;
scanf("%d", &T);
getchar();
for(i=0; i scanf("%d %d", &N, &M);
getchar();
head = (node *)malloc(sizeof(node)*N);
thead = NULL;
for(j=0; j head[j].job = 'A' + j;
head[j].color = WHITE;
head[j].d = MAX;
head[j].f = UNCHECKED;
head[j].next = NULL;
head[j].pre = NULL;
}
for(j=0; j scanf("%s", job);
getchar();
make_graph(head, job[0]-'A', job[1]-'A');
}
DFS(head, &thead, N);
t = thead;
j=0;
while(t != NULL) {
job[j] = t->job;
t = t->t_next;
j++;
}
job[j] = '\0';
printf("%s\n", job);
free(head);
}
return 0;
}