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;
}