글 읽기 - 질문합니다.

hsu2016 5년 전 0

유니온파인드로 풀려고 합니다.

혹시 어떤부분이 틀렸는지 알고 싶습니다.

대회때부터 지금까지 잡고 있는데 어디가 틀렸는지 모르겠네요ㅜㅜ

도와주세요

#include <iostream>
#include <set>
using namespace std;

int getParent(long long int parent[], int x) {
	if (parent[x] == x) {
		return x;
	}
	return parent[x] = getParent(parent, parent[x]);
}

void UnionParent(long long int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int findParent(long long int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) {
		return 1;
	}
	else {
		return 0;
	}
}
int main() {
	long long int parent[10001], N, M, K, *ptr, sum = 0, *temp;
	set<int> s;

	cin >> N >> M >> K;

	ptr = new long long int[N + 1];
	for (int i = 1; i <= N; i++) {
		cin >> ptr[i];
	}

	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		UnionParent(parent, a, b);
		if (findParent(parent, a, b)) {
			if (ptr[a] > ptr[b]) {
				ptr[a] = ptr[b];
			}
			else {
				ptr[b] = ptr[a];
			}
		}
	}

	for (int i = 1; i <= M; i++) {
		s.insert(parent[i]);
	}

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		sum = sum + ptr[*iter];
	}

	if (sum > K) {
		cout << "Oh no";
	}
	else {
		cout << sum;
	}
}

skqoaudgh 5년 전 1

친구관계가 없는 친구 인덱스가 있을 수 있습니다. (집합의 원소가 하나인 집합)

이 부분도 체크를 해주서야 할 것같네요

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

문제

문제

출처

ICPC

질문합니다.

hsu2016 5년 전 0

skqoaudgh 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말