글 읽기 - 크루스칼 알고리즘의 구현이 정확한지 확인해주시길 부탁드리겠습니다.

Rose 5년 전 0

힙으로 간선 가중치 순으로 정렬한다.
만약 둘중 하나가 연결이 안된 정점이라면 연결해준다.
둘다 어느 집합에 속해있는데 둘이 집합이 다르다면 더 적은 개수를 가진곳을 더 많은 개수를 가진곳에다 병합한다.

이렇게 하는것이 맞나요??

꼭 답변 부탁드리겠습니다!!

#include<stdio.h>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
struct _ed {
	int val,x, y;
};
bool operator<(_ed a, _ed b) {
	return a.val > b.val;
}
long long sum = 0;
vector<vector<int> >vec;
priority_queue<_ed>q;
int cyc[1004],cycle=1;
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int s, e, val;
		scanf("%d %d %d", &s, &e, &val);
		q.push({ val,s,e });
	}
	while (!q.empty()) {
		_ed a = q.top();
		q.pop();
		if (cyc[a.x]!=0&&cyc[a.x] == cyc[a.y])//사이클 돈다!
			continue;
		if(cyc[a.x]==0&&cyc[a.y]==0){//새로운 집합
			cyc[a.x] = cycle;
			cyc[a.y] = cycle;
			vec.push_back({ a.x,a.y });
			cycle++;
		}
		else if (cyc[a.x] == 0 && cyc[a.y] != 0) {//집합 추가
			cyc[a.x] = cyc[a.y];
			vec[cyc[a.y]-1].push_back(a.x);
		}
		else if (cyc[a.x] != 0 && cyc[a.y] == 0) {//집합 추가
			cyc[a.y] = cyc[a.x];
			vec[cyc[a.x]-1].push_back(a.y);
		}
		else {//집합 합체
			if (vec[cyc[a.x] - 1].size() > vec[cyc[a.y] - 1].size()) swap(a.x, a.y);
				int c = cyc[a.x] - 1;
				for (int i = 0; i < vec[c].size(); i++) {
					cyc[vec[c][i]] = cyc[a.y];
					vec[cyc[a.y] - 1].push_back(vec[c][i]);
				}
		}
		sum += a.val;
	}
	printf("%lld", sum);
	return 0;
}

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

문제

문제

출처

ICPC

크루스칼 알고리즘의 구현이 정확한지 확인해주시길 부탁드리겠습니다.

Rose 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말