글 읽기 - 크루스칼 알고리즘? 왜 틀릴까요

his130 6년 전 0

크루스칼 알고리즘을 이용했습니다.

find 와 merge 함수를 만들었고,

map을 이용하여 자동적으로 오름차순이 되도록 만들었습니다.

for문을 통해서 간선을 모두 방문하되,

같은 집합이면 continue;

다른 집합이면 답에 값을 추가해주면서

간선이 노드의 갯수 -1 , 즉 n-1 이 되면 나오도록 설정했습니다..

어디가 틀린건지 잘 모르겠습니다..도와주세요

#include<iostream>
#include<algorithm>
#include<map>

using namespace std;
int p[1001];
int find(int x)
{
	if (p[x] == x)
	{
		return x;
	}
	else
	{
		return p[x] = find(p[x]);
	}
}
void merge(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x == y)
	{
		return;
	}

	p[y] = x;
	return;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	map<int, pair<int, int>> v;
	for (int i = 1; i <= n; i++)
	{
		p[i] = i;
	}
	while (m--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		v[c] = { a,b };
	}
	int ans = 0;
	int cnt = 0;
	map<int, pair<int, int>>::iterator iter;
	for (iter = v.begin(); iter != v.end(); iter++)
	{
		int x = (*iter).second.first;
		int y = (*iter).second.second;

		if (find(x) == find(y))
		{
			continue;
		}

		merge(x, y);
		cnt++;
		ans += (*iter).first;

		if (cnt == n - 1)
		{
			break;
		}
	}

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

	return 0;
}

djm03178 6년 전 1

map은 중복되는 값을 다 저장하지 않습니다.

1 2 1

2 3 1

his130 6년 전 0

아.. 잊고있었네요 감사합니다..!

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

문제

문제

출처

ICPC

크루스칼 알고리즘? 왜 틀릴까요

his130 6년 전 0

djm03178 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말