1197 MST
알고리즘(크루스칼 알고리즘 사용)
1
2
3
4
5
6
1. 가장 가중차가 작은 간선부터 검사
2. 사이클 검사
1. 간선의 양단이 전부 이미 안들어갔으면 양단을 같은 벡터에 집어넣고, set 벡터에 집어넣음
2. 한쪽만 들어갔다면, 들어가 있는 한쪽의 set벡터에 안들어간 쪽을 집어넣음
3. 두개 다 들어가 있고, 들어간 집합이 같다면, 사이클 형성 -> false 반환
4. 두개 다 들어가 있고, 들어간 집합이 다르다면, 두개를 합침.
자료구조
1
2
3
간선을 저장하는 Edge 배열
노드를 저장하는 Node 배열. - 배열의 인덱스가 노드의 번호이고, 저장돼있는 정보는 들어가있는 셋의 번호. 아직 포함안됐으면 -1
셋을 저장하는 set 벡터 - vector<vector<int>> set 으로 선언하여, set안에 각 vector<int>는 하나의 집합을 표현.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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;
}