[해커랭크] Kruskal (MST): Really Special Subtree (C++)

문제링크: www.hackerrank.com/challenges/kruskalmstrsub/problem

Kruskal (MST): Really Special Subtree | HackerRank

1. 주의할 점

- 간선의 가중치가 같다면 각 Node의 합이 작은것을 우선시한다

- Make_union() 함수에서 부모를 잘 갱신하도록 한다

 

2. 구현

- 입력받는 모든 간선에 대한 정보를 우선순위큐 PQ에 넣는다

- PQ에서 꺼낸 간선에서 양 끝점이 만약 같은 집합이 아니라면 Make_union()함수를 통해 이어주며 Result에는 가중치만큼 더하며 Cnt++를 통해 MST의 경우 Node의 개수-1만큼의 간선이 이어지면 된다는 점을 이용하여 While문을 더 빨리 빠져나올 수 있도록 한다

struct info {
	int s, e, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.val == b.val)
			return a.s + a.e > b.s + b.e;
		return a.val > b.val;
	}
};
info tmp;
int par[3001];
int find_par(int x) {
	if (par[x] == x) return x;
	return par[x] = find_par(par[x]);
}

void make_union(int a, int b) {
	int pa = find_par(a);
	int pb = find_par(b);
	if (pa < pb) 
		par[pb] = pa;	
	else if (pa > pb) 
		par[pa] = pb;	
}

int kruskals(int g_nodes, vector<int> g_from, vector<int> g_to, vector<int> g_weight) {
	priority_queue<info, vector<info>, cmp> pq;
	//초기화
	for (int i = 1; i <= g_nodes; i++)
		par[i] = i;
	int result = 0;
	for (int i = 0; i < g_from.size(); i++) {
		tmp.s = g_from[i];
		tmp.e = g_to[i];
		tmp.val = g_weight[i];
		pq.push(tmp);
	}
	int cnt = 0;
	while (!pq.empty()) {
		int cs = pq.top().s;
		int ce = pq.top().e;
		int cv = pq.top().val;
		pq.pop();
		int ps = find_par(cs);
		int pe = find_par(ce);
		if (ps == pe) continue;
		make_union(cs, ce);
		result += cv;
		cnt++;
		if (cnt == g_nodes - 1) break;
	}
	return result;
}