Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <algorithm>
- int n, m;
- std::vector<std::vector<int> > list(m);
- struct compare{
- bool operator() (std::vector<int> a, std::vector<int> b) {
- return a[0] < b[0];
- }
- } compare;
- void constructor() {
- std::vector<int> v;
- int start, finish, cost;
- for (size_t i = 0; i != m; i++) {
- std::cin >> start >> finish >> cost;
- v.push_back(cost);
- v.push_back(start);
- v.push_back(finish);
- // for (size_t i = 0; i < v.size(); i++) {
- // std::cout << v[i] << " ";
- // }
- list.push_back(v);
- v = {};
- }
- }
- void make_set(std::vector<int> &parent) {
- for (size_t i = 0; i != list.size(); i++) {
- if (parent[list[i][1]] == 0) {
- parent[list[i][1]] = list[i][1];
- }
- if (parent[list[i][2]] == 0) {
- parent[list[i][2]] = list[i][2];
- }
- }
- }
- int find_set(int verties, std::vector<int> &parent) {
- if (verties == parent[verties]) {
- return verties;
- }
- return parent[verties] = find_set(parent[verties], parent);
- }
- void union_sets(int parent_a, int parent_b, std::vector<int> &parent, std::vector<int> &rank) {
- if (parent_a != parent_b) {
- if (rank[parent_a] < rank[parent_b]) {
- std::swap(parent_a, parent_b);
- }
- parent[parent_b] = parent_a;
- if (rank[parent_a] == rank[parent_b]) {
- rank[parent_a]++;
- }
- }
- }
- void Kruskal(std::vector<int> &parent, std::vector<int> &rank) {
- int number = 0, price = 0;
- for (size_t i = 0; i != list.size(); i++) {
- if (find_set(list[i][2], parent) != find_set(list[i][1], parent)) {
- union_sets(find_set(list[i][2], parent), find_set(list[i][1], parent), parent, rank);
- if (list[i][0] != 0) {
- price = price + list[i][0];
- number++;
- }
- }
- }
- std::cout << "\n" << price << " " << number;
- }
- int main() {
- std::cin >> n >> m;
- std::vector<int> rank(n + 1);
- std::vector<int> parent(n + 1);
- constructor();
- std::sort(list.begin(), list.end(), compare);
- make_set(parent);
- Kruskal(parent, rank);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement