글 읽기 - 시간 초과나는 이유 알 수 있을까요?

parkcs1220 3년 전 0

시간 초과 나는 이유를 못 찾겠습니다.

#include <stdio.h>
#define MAX_VERTICES 10000+1
#define MAX_EDGES 100000

int parent[MAX_VERTICES];
int num[MAX_VERTICES];

void set_init(int n) {
	int i;
	for (i = 0; i <= n; i++) {
		num[i] = 1;
		parent[i] = -1;
	}
}

int set_find(int vertex) {
	int i, s, p;

	for (i = vertex; p=parent[i] >= 0; i = p)
		;

	s = i;

	for (i = vertex; (p = parent[i]) >= 0; i = p)
		parent[i] = s;

	return s;
}

void set_union(int s1, int s2) {
	int root_s1 = set_find(s1);
	int root_s2 = set_find(s2);

	if (root_s1 != root_s2) {
		if (num[root_s1] < num[root_s2]) {
			parent[root_s1] = root_s2;
			num[root_s2] += num[root_s1];
		}
		else {
			parent[root_s2] = root_s1;
			num[root_s1] += num[root_s2];
		}
	}
}

typedef struct {
	int p;
	int q;
	int key;
} element;

typedef struct {
	element heap[MAX_EDGES];
	int heap_size;
} HeapType;

void init(HeapType* h) {
	h->heap_size = 0;
}

void insert_edge(HeapType* h, int a, int b, int c) {
	int i;
	element item;
	item.p = a;
	item.q = b;
	item.key = c;
	i = ++(h->heap_size);
	while (i > 1 && h->heap[i / 2].key > item.key) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}

element delete_min_heap(HeapType* h) {
	element item = h->heap[1];
	element temp = h->heap[(h->heap_size)--];
	int parent = 1;
	int child = 2;
	while (child <= h->heap_size) {
		if (child + 1 <= h->heap_size && h->heap[child].key > h->heap[child + 1].key)
			child = child + 1;
		if (h->heap[child].key > temp.key)
			break;
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

int kruskal(int n, HeapType* h) {
	int cost = 0;
	int edge_accepted = 0;
	element e;
	while (edge_accepted < (n-1)) {
		e = delete_min_heap(h);
		if (set_find(e.p) != set_find(e.q)) {
			set_union(e.p, e.q);
			cost += e.key;
			edge_accepted++;
		}
	}
	return cost;
}


int main() {
	int v, e;
	int a, b, c;
	int i;
	HeapType h;

	scanf("%d %d", &v, &e);

	set_init(v);
	init(&h);

	for (i = 0; i < e; i++) {
		scanf("%d %d %d", &a, &b, &c);
		insert_edge(&h, a, b, c);
	}

	printf("%d", kruskal(v, &h));

	return 0;
}

parkcs1220 3년 전 0

int set_find(int vertex) {

if (parent[vertex] == vertex) return vertex;

else return set_find(parent[vertex]);

}

parkcs1220 3년 전 0

int set_find(int vertex) {

int i;

for (i = vertex; parent[i] >= 0; i = parent[i])

;

return i;

}

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

문제

문제

출처

ICPC

시간 초과나는 이유 알 수 있을까요?

parkcs1220 3년 전 0

parkcs1220 3년 전 0

parkcs1220 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말