글 읽기 - 이게 왜 메모리초과죠????????????????????????????????

smu04129 2년 전 0

이해가 안갑니다...

아무리 봐도 안보입니다.

벽에다 대가리 박으면서 비명지르다 질문 올려봅니다...

사이클은 유니온 파인드를 통해 체크해주고

트리수는 셋을 통해 존재하는 부모들을 저장해주어 - 1 해주었습니다.

#include <unordered_set>
#include <iostream>
#include <vector>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define MAX 100001
using namespace std;

int N, M;
int Parent[MAX];
unordered_set<int> S;

int get_parent(int cur) {
	if (Parent[cur] == cur) { return cur; }
	return Parent[cur] = get_parent(cur);
}

bool is_union_(int a, int b) { return get_parent(a) == get_parent(b) ? true : false; }

void union_(int a, int b) {
	int pa = get_parent(a), pb = get_parent(b);
	Parent[b] = pa;
}

int main() {
	fast_io;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) { Parent[i] = i; }
	int cnt = 0;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		if (is_union_(u, v)) { cnt++; }
		else { union_(u, v); }
	}
	for (int i = 1; i <= N; i++)
		if (S.find(Parent[i]) == S.end()) { S.insert(Parent[i]); }
	cout << cnt + S.size() - 1;
}

jinhan814 2년 전 1

1. 15번 줄을 return Parent[cur] = get_parent(Parent[cur])로 고쳐줘야 합니다. get_parent(cur)에서 get_parent(cur)를 계속 호출한다면 무한루프가 생겨서 스택 메모리가 초과되어 메모리 초과를 받습니다.

2. 22번 줄을 Parent[pb] = pa로 고쳐야 합니다.

3. 37번 줄에서 Parent[i]는 아직 경로압축이 되지 않아서 i번 정점이 속하는 집합의 루트를 나타내지 않을 수 있습니다. 따라서 Parent[i] 대신 get_parent(i)를 사용해야 합니다.

1, 2, 3번을 고쳐주면 AC를 받습니다. (코드 : http://boj.kr/2e481005f6f44628...)

smu04129 1년 전 1

감사합니다 덕분에 많이 배우고 갑니다

감사해요 ㅠㅠ

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

문제

문제

출처

ICPC

이게 왜 메모리초과죠????????????????????????????????

smu04129 2년 전 0

jinhan814 2년 전 1

smu04129 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말