FilesExpand file tree

master

/

8.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (51 loc) · 1.8 KB

master

/

8.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (51 loc) · 1.8 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#include <bits/stdc++.h>

using namespace std;

// 노드의 개수와 간선(Union 연산)의 개수 입력받기

int v, e;

int parent[100001]; // 부모 테이블 초기화

// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수

vector<pair<int, pair<int, int> > > edges;

int result = 0;

// 특정 원소가 속한 집합을 찾기

int findParent(int x) {

// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출

if (x == parent[x]) return x;

return parent[x] = findParent(parent[x]);

}

// 두 원소가 속한 집합을 합치기

void unionParent(int a, int b) {

a = findParent(a);

b = findParent(b);

if (a < b) parent[b] = a;

else parent[a] = b;

}

int main(void) {

cin >> v >> e;

// 부모 테이블상에서, 부모를 자기 자신으로 초기화

for (int i = 1; i <= v; i++) {

parent[i] = i;

}

// 모든 간선에 대한 정보를 입력 받기

for (int i = 0; i < e; i++) {

int a, b, cost;

cin >> a >> b >> cost;

// 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정

edges.push_back({cost, {a, b}});

}

// 간선을 비용순으로 정렬

sort(edges.begin(), edges.end());

int last = 0; // 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선

// 간선을 하나씩 확인하며

for (int i = 0; i < edges.size(); i++) {

int cost = edges[i].first;

int a = edges[i].second.first;

int b = edges[i].second.second;

// 사이클이 발생하지 않는 경우에만 집합에 포함

if (findParent(a) != findParent(b)) {

unionParent(a, b);

result += cost;

last = cost;

}

}

cout << result - last << '\n';

}