글 읽기 - union find 로 하면 왜 안될까요...??

carpediem804 3년 전 0

union find를 써서

각 노드 별 연결 개수를 vector 에 저장 후 내림차순으로 정렬하여

k의 값에서 뺄수 있으면 빼는 것으로 계산을 했는데

11%에서 틀렷다고 나옵니다

어떠한 경우에서 틀릴수가있는지 제 부족한 머리로는 이해가 가지않습니다...ㅠㅠ

똑똑하신 분들의 도움이 필요합니다 ㅠㅠ 도와주세요 ㅠㅠ

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int map[1001];
int n, k;
int root_map[1001];
int cnt_map[1001];
vector<int> v;
int find_root(int a) {
	if (a == root_map[a]) {
		return a;
	}
	else {
		return root_map[a] = find_root(root_map[a]);
	}

}
void union_(int a, int b) {//a와 b를 한 집합으로 만들기 
	int a_root = find_root(a);
	int b_root = find_root(b);
	if (a_root != b_root) {
		root_map[b_root] = a_root;
	}
}
int main(void) {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf(" %d", &map[i]);
	}
	for (int i = 1; i <= n; i++) {
		root_map[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		union_(i, map[i]);
	}
	for (int i = 1; i <= n; i++) {
		cnt_map[find_root(root_map[i])] += 1;
		//printf("%d ", root_map[i]);
	}
	//printf("\n");
	
	for (int i = 1; i <= n; i++) {
		if (cnt_map[i] != 0 && cnt_map[i]<=k) {
			v.push_back(cnt_map[i]);
		}
	}
	sort(v.begin(), v.end(),greater<int>());
	int ans = 0;
	for (int i = 0; i <v.size(); i++) {
		if (k >= v[i]) {
			k -= v[i];
			ans += v[i];
		}
		//printf("%d ", v[i]);
	}
	//printf("\n\n");
	printf("%d\n", ans);


	return 0;
}

lovinix 3년 전 0

푼 문제는 아니지만

4 3

1 1 1 1

답은 3이나와야할거같네요

carpediem804 3년 전 0

아 그렇네요 제가 문제를 잘못이해를 했네요.... 감사합니다 ㅠㅠ

blou888 1년 전 0

문제를 이해를 못해서 그런가,

모든 사람이 불만이 안 생기도록 할려면, 4명이 한 버스에 타야 하는 것 아닌가요?

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

문제

문제

출처

ICPC

union find 로 하면 왜 안될까요...??

carpediem804 3년 전 0

lovinix 3년 전 0

carpediem804 3년 전 0

blou888 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말