1197 MST

์•Œ๊ณ ๋ฆฌ์ฆ˜(ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‚ฌ์šฉ)

1. ๊ฐ€์žฅ ๊ฐ€์ค‘์ฐจ๊ฐ€ ์ž‘์€ ๊ฐ„์„ ๋ถ€ํ„ฐ ๊ฒ€์‚ฌ
2. ์‚ฌ์ดํด ๊ฒ€์‚ฌ
	1. ๊ฐ„์„ ์˜ ์–‘๋‹จ์ด ์ „๋ถ€ ์ด๋ฏธ ์•ˆ๋“ค์–ด๊ฐ”์œผ๋ฉด ์–‘๋‹จ์„ ๊ฐ™์€ ๋ฒกํ„ฐ์— ์ง‘์–ด๋„ฃ๊ณ , set ๋ฒกํ„ฐ์— ์ง‘์–ด๋„ฃ์Œ
	2. ํ•œ์ชฝ๋งŒ ๋“ค์–ด๊ฐ”๋‹ค๋ฉด, ๋“ค์–ด๊ฐ€ ์žˆ๋Š” ํ•œ์ชฝ์˜ set๋ฒกํ„ฐ์— ์•ˆ๋“ค์–ด๊ฐ„ ์ชฝ์„ ์ง‘์–ด๋„ฃ์Œ
	3. ๋‘๊ฐœ ๋‹ค ๋“ค์–ด๊ฐ€ ์žˆ๊ณ , ๋“ค์–ด๊ฐ„ ์ง‘ํ•ฉ์ด ๊ฐ™๋‹ค๋ฉด, ์‚ฌ์ดํด ํ˜•์„ฑ -> false ๋ฐ˜ํ™˜
	4. ๋‘๊ฐœ ๋‹ค ๋“ค์–ด๊ฐ€ ์žˆ๊ณ , ๋“ค์–ด๊ฐ„ ์ง‘ํ•ฉ์ด ๋‹ค๋ฅด๋‹ค๋ฉด, ๋‘๊ฐœ๋ฅผ ํ•ฉ์นจ.

์ž๋ฃŒ๊ตฌ์กฐ

๊ฐ„์„ ์„ ์ €์žฅํ•˜๋Š” Edge ๋ฐฐ์—ด
๋…ธ๋“œ๋ฅผ ์ €์žฅํ•˜๋Š” Node ๋ฐฐ์—ด. - ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๊ฐ€ ๋…ธ๋“œ์˜ ๋ฒˆํ˜ธ์ด๊ณ , ์ €์žฅ๋ผ์žˆ๋Š” ์ •๋ณด๋Š” ๋“ค์–ด๊ฐ€์žˆ๋Š” ์…‹์˜ ๋ฒˆํ˜ธ. ์•„์ง ํฌํ•จ์•ˆ๋์œผ๋ฉด -1
์…‹์„ ์ €์žฅํ•˜๋Š” set ๋ฒกํ„ฐ - vector<vector<int>> set ์œผ๋กœ ์„ ์–ธํ•˜์—ฌ, set์•ˆ์— ๊ฐ vector<int>๋Š” ํ•˜๋‚˜์˜ ์ง‘ํ•ฉ์„ ํ‘œํ˜„.

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX_EDGE 1000000
#define MAX_NODE 10000
 
using namespace std;
 
typedef struct Edge {
	int node1;
	int node2;
	int value;
 
	bool operator < (Edge e) {
		return value < e.value;
	}
} Edge;
 
Edge edge[MAX_EDGE];
int nodeSetNum[MAX_NODE];
vector<vector<int>> set;
int numOfNode, numOfEdge;
 
long long getMST();
bool unionFind(int index);
 
int main() {
	cin >> numOfNode >> numOfEdge;
	for (int i = 0; i < numOfEdge; i++)
		cin >> edge[i].node1 >> edge[i].node2 >> edge[i].value;
	for (int i = 0; i < numOfEdge; i++) {
		edge[i].node1;
		edge[i].node2;
	}
 
	cout << getMST();
}
 
long long getMST() {
	sort(edge, &edge[numOfEdge]);
	memset(nodeSetNum, -1, sizeof(nodeSetNum));
	long long sum = 0;
	int edgeCount = 0;
	for(int i = 0; i<numOfEdge; i++) {
		if (unionFind(i)) {
			sum += edge[i].value;
			edgeCount++;
		}
		//๋…ธ๋“œ ๊ฐœ์ˆ˜ -1 ์ด๋ฉด ํŠธ๋ฆฌ์™„์„ฑ
		if (edgeCount == numOfNode - 1)
			break;
	}
 
	return sum;
}
 
bool unionFind(int index) {
	if (nodeSetNum[edge[index].node1] == -1 && nodeSetNum[edge[index].node2] == -1) {
		vector<int> temp;
		temp.push_back(edge[index].node1);
		temp.push_back(edge[index].node2);
		set.push_back(temp);
		nodeSetNum[edge[index].node1] = set.size() - 1;
		nodeSetNum[edge[index].node2] = set.size() - 1;
	}
	else if (nodeSetNum[edge[index].node1] == -1) {
		nodeSetNum[edge[index].node1] = nodeSetNum[edge[index].node2];
		set[nodeSetNum[edge[index].node1]].push_back(edge[index].node1);
	}
	else if (nodeSetNum[edge[index].node2] == -1) {
		nodeSetNum[edge[index].node2] = nodeSetNum[edge[index].node1];
		set[nodeSetNum[edge[index].node2]].push_back(edge[index].node2);
	}
	else if (nodeSetNum[edge[index].node1] == nodeSetNum[edge[index].node2])
		return false;
	else {
		if (nodeSetNum[edge[index].node1] < nodeSetNum[edge[index].node2]) {
			vector<int> move = set[nodeSetNum[edge[index].node2]];
			for (int i = 0; i < move.size(); i++) {
				nodeSetNum[move[i]] = nodeSetNum[edge[index].node1];
				set[nodeSetNum[edge[index].node1]].push_back(move[i]);
			}
		}
		else {
			vector<int> move = set[nodeSetNum[edge[index].node1]];
			for (int i = 0; i < move.size(); i++) {
				nodeSetNum[move[i]] = nodeSetNum[edge[index].node2];
				set[nodeSetNum[edge[index].node2]].push_back(move[i]);
			}
		}
	}
	return true;
}