글 읽기 - 크루스칼 알고리즘 사용 중 왜 틀린지 모르겠습니다.ㅜㅜㅜ 부탁드립니다.크

shs2810 5년 전 0

크루스칼 알고리즘인데...

어디가 잘못되었을까요? ㅜㅜㅜㅜ

컴파일하면 틀렸다고 이야기를 해요..

 #include<iostream>
 #include<algorithm>
 #include<vector>
 
 using namespace std;
 
 int getParent(int parent[], int x) {
 	if(parent[x] == x) {
 		return x;
	 } else {
	 	parent[x] = getParent(parent, parent[x]);
	 }
 }
 
 void unionParent(int parent[], int x, int y) {
 	x = getParent(parent, x);
 	y = getParent(parent, y);
 	if(x<y) {
 		parent[y] = x;
	 } else {
	 	parent[x] = y;
	 }
 }
 
 int findParent(int parent[], int x, int y) {
 	x = getParent(parent, x);
 	y = getParent(parent, y);
 	if(x == y) {
 		return 1;
	 } else {
	 	return 0;
	 }
 }
 
 class Edge {
 	public : 
 		int node[2];
 		long long distance;
 		Edge(int a, int b, long long distance) {
 			this->node[0] = a;
 			this->node[1] = b;
 			this->distance = distance;
		 }
		 
		 bool operator <(Edge &edge) {
		 	return this->distance < edge.distance;
		 }
 };
 
 
 vector<pair<int, int> > v;
 
 int main(void) {
 	int n, m;
	long long sum=0;
 	vector<Edge> v;
	
	scanf("%d %d", &n, &m);
	
	for(int i=0; i<m; i++) {
		int a, b;
		long long distance;
		scanf("%d %d %lld", &a, &b, &distance);
		v.push_back(Edge(a, b, distance));
	}
	
	sort(v.begin(), v.end());	
		
	int parent[1001];	
	for(int i=1; i<=n; i++) {
		parent[i] = i;
	}
	
	for(int i=0; i<v.size(); i++) {
		if(!findParent(parent, v[i].node[0], v[i].node[1])) {
			sum += v[i].distance;
			unionParent(parent, v[i].node[0], v[i].node[1]);
		}
	}
	
	printf("%lld\n", sum);
	
	
 } 

shs2810 5년 전 0

아 return 을 빼뜨렸네요.. ㅜㅜ

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

문제

문제

출처

ICPC

크루스칼 알고리즘 사용 중 왜 틀린지 모르겠습니다.ㅜㅜㅜ 부탁드립니다.크

shs2810 5년 전 0

shs2810 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말