글 읽기 - 런타임 에러 질문드립니다

star2770 8년 전 0

vs에서는 문제없이 잘 돌아가는데

왜 런타임 에러가 날까요??

#include <stdio.h>
#include <stdlib.h>


typedef struct node{
	int a;
	int b;
	int c;
}edge;

void quicksort(edge*list, int start, int end);
int find(int x);
void unite(int a, int b);

int *par;
int *rank;

int main(void){
	int v,e,i;
	int result=0,edgen=0;
	int x,y;
	edge *arr;
	scanf("%d %d",&v,&e);
	arr=(edge *)malloc(sizeof(edge)*e);
	par=(int*)malloc(sizeof(int)*(v+1));
	rank=(int*)malloc(sizeof(int)*(v+1));
	for(i=1;i<=v;i++){
		rank[i]=0;
		par[i]=i;
	}
	for(i=0;i<e;i++){
		scanf("%d %d %d",&arr[i].a,&arr[i].b,&arr[i].c);
	}
	quicksort(arr,0,e-1);
	i=0;
	while(edgen!=v-1 ){
		x=find(arr[i].a);
		y=find(arr[i].b);
		if(x!=y){
			edgen++;
			result+=arr[i].c;
			unite(arr[i].a,arr[i].b);
		}
		i++;
	}
	printf("%d\n",result);
	free(arr);
	free(par);
	free(rank);

}

int find(int x){
	if(par[x]==x) return x;
	else return par[x]=find(par[x]);
}

void unite(int a, int b){
	a=find(a);
	b=find(b);
	if(a==b) return;
	if(rank[a]<rank[b])
		par[a]=b;
	else{
		par[b]=a;
		if(rank[a]==rank[b])
			rank[a]++;
	}
}

void swap(edge *x, edge *y){
	edge temp;
	temp=*x;
	*x=*y;
	*y=temp;
}

void quicksort(edge*list, int start, int end){
	int mid,p,q;
	edge pivot;
	if(start>=end) return;
	mid=(start+end)/2;
	pivot=list[mid];
	swap(&list[start],&list[mid]);
	p=start+1;
	q=end;
	while(1){
		while(list[p].c<=pivot.c) p++;
		while(list[q].c>pivot.c) q--;
		if(p>q) break;
		swap(&list[p],&list[q]);
	}
	swap(&list[start],&list[q]);
	quicksort(list,start,q-1);
	quicksort(list,q+1,end);
}

Nada 8년 전 1

quicksort 구현이 잘못되서 런타임에러가 발생하네요

sort부분만 수정했더니 맞았습니다.

그리고 추가적으로 unite의 rank 연산이 잘못되었습니다.

rank 최적화를 안해도 nlogn정도의 시간을 보이지만 rank[a] += rank[b]를 하는 과정을 추가해야

원하시는 최적화 과정이 이루어질 것 같네요.

star2770 8년 전 0

감사합니다! 덕분에 해결 잘했습니다~

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

문제

문제

출처

ICPC

런타임 에러 질문드립니다

star2770 8년 전 0

Nada 8년 전 1

star2770 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말