글 읽기 - 예외 케이스가 있는지 궁금합니다.

cls327 7년 전 0

인접리스트를 이용해서 풀었구요. 간선들을 입력받고 정렬해서 간선을 삽입하게 하였습니다. 어디가 잘못됬죠??

#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
	int data;
	struct ListNode *Llink,*Rlink;
}ListNode;

typedef struct {
	ListNode *front, *rear;
}QueueType;

typedef struct {
	int u,v;
}element;

ListNode *adj_list[1001];
int DFS_visited[1001], BFS_visited[1001];
element edge[10000];

void init_queue(QueueType *q) {
	q->front = q->rear = NULL;
}
void init_adj_list(int n) {
	int i;
	for (i = 1; i <= n; i++) {
		ListNode *nullnode = (ListNode*)malloc(sizeof(ListNode));
		nullnode->data = NULL;
		nullnode->Llink = nullnode;
		nullnode->Rlink = nullnode;
		adj_list[i] = nullnode;
	}
}
void insert_edge(int u, int v) {
	ListNode *newnode = (ListNode*)malloc(sizeof(ListNode));
	ListNode *newnode2 = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = v;
	newnode->Llink = adj_list[u]->Llink;
	newnode->Rlink = adj_list[u];
	adj_list[u]->Llink->Rlink = newnode;
	adj_list[u]->Llink = newnode;

	newnode2->data = u;
	newnode2->Llink = adj_list[v]->Llink;
	newnode2->Rlink = adj_list[v];
	adj_list[v]->Llink->Rlink = newnode2;
	adj_list[v]->Llink = newnode2;
}
void enqueue(QueueType *q, int data) {
	ListNode *newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = data;
	newnode->Rlink = newnode->Llink = NULL;
	if (q->front == NULL) q->front = q->rear = newnode;
	else {
		q->rear->Rlink = newnode;
		q->rear = newnode;
	}
}
ListNode* dequeue(QueueType *q) {
	ListNode *temp;
	if (q->front == NULL) return;
	temp = q->front;
	q->front = q->front->Rlink;

	return temp;
}
void BFS(int start) {
	QueueType q;
	ListNode *u, *v;
	init_queue(&q);
	BFS_visited[start] = 1;
	enqueue(&q, start);
	while (q.front != NULL) {
		u = dequeue(&q);
		printf("%d ", u->data);
		for(v = adj_list[u->data]->Rlink;v->data!=NULL;v=v->Rlink){
			if (!BFS_visited[v->data]) {
				BFS_visited[v->data] = 1;
				enqueue(&q, v->data);
			}
		}
	}
}

void DFS(int u) {
	ListNode *v;
	DFS_visited[u] = 1;
	printf("%d ", u);
	for (v = adj_list[u]->Rlink; v->data != NULL; v = v->Rlink) {
		if (!DFS_visited[v->data]) DFS(v->data);
	}
}
void sort(int n) {
	int i, j;
	element temp;
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			if (edge[i].u > edge[j].u) {
				temp = edge[j];
				edge[j] = edge[i];
				edge[i] = temp;
			}
		}
	}
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			if (edge[i].u == edge[j].u && edge[i].v > edge[j].v) {
				temp = edge[j];
				edge[j] = edge[i];
				edge[i] = temp;
			}
		}
	}
}
int main() {
	int vertex, C_edge, start, i;
	scanf("%d %d %d", &vertex, &C_edge, &start);
	init_adj_list(vertex);
	for (i = 0; i < C_edge; i++) scanf("%d %d", &edge[i].u, &edge[i].v);
	sort(C_edge);
	for (i = 0; i < C_edge; i++) insert_edge(edge[i].u, edge[i].v);
	DFS(start);
	printf("\n");
	BFS(start);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예외 케이스가 있는지 궁금합니다.

cls327 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말