글 읽기 - [최소 스패닝 트리] 런타임 에러 질문있습니다.

park780172 4년 전 0

저번에 풀었을 때는 바로 통과하였는데

(저번 코드 : http://boj.kr/e9c58f240ce7480f...)

이번 코드에서는 계속 런타임 에러가 발생하네요..

메모리 제한 때문은 아닌 것 같은데 런타임 에러 원인을 잘 모르겠습니다.

(배열 범위를 100001로 해도 런타임 에러가 발생합니다.)

저번 코드와 이번 코드의 차이점도 잘 모르겠네요.

답변해주시면, 감사하겠습니다.

#include <bits/stdc++.h>

using namespace std;

#define Max 10001

typedef struct info
{
	int weigth, from, to;
}info;

vector<info> v;
int V, E, p[Max];

bool cmp(const info & a, const info & b)
{
	return a.weigth < b.weigth;
}

int Find(int x)
{
	if (x == p[x]) return x;
	else p[x] = Find(p[x]);
}

void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);
	if (a < b) p[b] = a;
	else p[a] = b;
}

int main()
{
	//freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
	cin.tie(0);
	scanf("%d %d", &V, &E);

	for (int i = 1; i <= V; i++) p[i] = i; // 초기화

	int f, t, w, ans = 0;

	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &f, &t, &w);
		v.push_back({ w, f, t }); // 가중치, 출발, 도착
	}

	sort(v.begin(), v.end(), cmp); // 가중치 기준으로 오름차순 정렬

	int cnt = 0;

	for (auto i : v) {
		if (Find(i.from) != Find(i.to)) { // 사이클이 아니라면
			Union(i.from, i.to); // 결합
			ans += i.weigth;
			//if (++cnt == V - 1) break; // mst 조건
		}
	}

	printf("%d\n", ans);

	return 0;
}

snrnsidy 4년 전 1

else p[x] = Find(p[x]); 이 부분이 문제인듯 싶네요.

park780172 4년 전 0

헉 이런 실수를... 감사합니다ㅠ

temp1234 4년 전 0

안녕하세요 저도 이 부분 때문에 런타임 에러가 나는 것 같은데 혹시 왜 이게 런타임 에러가 나는지 알려주실 수 있으신가요? 이해가 안 가네요..ㅠㅠ

else p[x] = Find(p[x]);

park780172 4년 전 1

Find() 함수는 return을 해야합니다.

else p[x] = Find(p[x]);

위의 코드는 압축만 할 뿐, return을 하지 않고 있습니다.

temp1234 4년 전 0

아아 그러네요 !! 정말 감사합니다 ㅎㅎㅎ

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

문제

문제

출처

ICPC

[최소 스패닝 트리] 런타임 에러 질문있습니다.

park780172 4년 전 0

snrnsidy 4년 전 1

park780172 4년 전 0

temp1234 4년 전 0

park780172 4년 전 1

temp1234 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말