글 읽기 - 크루스칼 어디가 틀린지 모르겠습니다 ㅜㅜ

baky94 4년 전 0

질문검색 반례도 다 해봤는데 어디서 틀리는 지 모르겠습니다 ㅜㅜ 헬프 요청합니다 ㅜㅜ

#include<stdio.h>
#define INF 987654321
#include<queue>
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>

using namespace std;



typedef struct point{
	long long data;
	int left;
	int right;
}point;

int n, m;
int result;
point p[100001];
int v[100001];

int sum=0;


bool cmp(const point &p1, const point &p2){
	if(p1.data<p2.data){
		return true;
	}
	else{
		return false;
	}
}

int find(int a){
	if(a == v[a])
		return a;
	return v[a] = find(v[a]);
}

bool check(int l, int r){
	l = find(l);
	r = find(r);
	if(l == r)
		return false;
	v[r] = l;
	return true;
	
}

void kruskal(){
	
	long long cnt=0;
	for(int i=0;i<n;i++){
		int l = p[i].left;
		int r = p[i].right;
		if(check(l, r)){
			cnt += p[i].data;
		}
	}
	printf("%lld\n",cnt);
	
}



int main(){
	
	scanf("%d", &n);
	scanf("%d", &m);
	
	
	int a,b,c;
	
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&a,&b,&c);
		p[i].left = a;
		p[i].right = b;
		p[i].data = c;
	}
	sort(p,p+n,cmp);
	for(int i=1;i<=n;i++){
		v[i] = i;
	}
	kruskal();
	
}

djm03178 4년 전 1

sort를 m개에 대해 해야 합니다.

baky94 4년 전 0

답변 감사합니다!!

sort(p,p+m,cmp);

로 해도 같은 결과가 나오네요 ㅜㅜ

djm03178 4년 전 0

kruskal 함수에서도 n개가 아니라 m개에 대해 돌려야 합니다.

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

문제

문제

출처

ICPC

크루스칼 어디가 틀린지 모르겠습니다 ㅜㅜ

baky94 4년 전 0

djm03178 4년 전 1

baky94 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말