Блог

Я пытался решить Минимальное связующее дерево на Каттисе. (https://open.kattis.com/problems/minspantree ) Первый тест выполняется нормально, второй выдает неопределенную ошибку во время выполнения. Я борюсь с этим уже больше недели. Это должна быть какая-то логическая ошибка, но независимо от того, сколько усилий я в нее вкладываю, я не вижу, что не так.

 #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

class DisjointSet {
public:
    vector<int> parent, rank;

    DisjointSet(int _size) {
        parent.resize(_size);
        rank.resize(_size); // Maybe this?
        // make the sets
        for (int i = 0; i < _size; i  ) { // fill set 
            parent[i] = i;
            rank[i] = 0;
        }
    }


    void make_set(int v) {
        parent[v] = v;
        rank[v] = 0;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (rank[a] < rank[b])
                swap(a, b);
            parent[b] = a;
            if (rank[a] == rank[b])
                rank[a]  ;
        }
    }

};
bool sort_weight(const tuple<int, int, int> amp;one, const tuple<int, int, int> amp;two) {
    return get<2>(one) < get<2>(two); // Weight
}
bool sort_node(const tuple<int, int, int> amp;one, const tuple<int, int, int> amp;two) {
    if (get<0>(one) != get<0>(two)) {
        return get<0>(one) < get<0>(two); // node one
    } 
    return get<1>(one) < get<1>(two); // node two
}

int main()
{

    int n_nodes = 0, n_arcs = 0;
    int tmp_node1, tmp_node2, tmp_weight;

    while (cin >> n_nodes >> n_arcs) { // Until the end
        if (n_nodes == 0 amp;amp; n_arcs == 0) { break; }
        if (n_arcs < n_nodes - 1) { // If it is not possible to build a MST
            cout << "Impossiblen";
        }
        else {
            int cost = 0;
            DisjointSet s(n_nodes); // make set
            vector<tuple<int, int, int>> vArcs;
            vector<tuple<int, int, int>> vResu<
            vArcs.resize(n_arcs);

            for (int i = 0; i < n_arcs; i  ) {
                cin >> tmp_node1 >> tmp_node2 >> tmp_weight;
                vArcs[i] = make_tuple(tmp_node1, tmp_node2, tmp_weight);
            }


            sort(vArcs.begin(), vArcs.end(), sort_weight); // Sort by weight lowest to highest

            for (int i = 0; i < n_arcs amp;amp; vResult.size()<(n_nodes - 1); i  )
            {
                if (s.find_set(get<0>(vArcs[i])) != s.find_set(get<1>(vArcs[i]))) {
                    cost  = get<2>(vArcs[i]);
                    vResult.push_back(vArcs[i]);
                    s.union_sets(get<0>(vArcs[i]), get<1>(vArcs[i]));
                }
            }
            // We are done, order and print
            sort(vResult.begin(), vResult.end(), sort_node);
            cout << cost << "n";
            for (int i = 0; i < vResult.size(); i  )
            {
                cout << get<0>(vResult[i]) << " " << get<1>(vResult[i]) << "n";
            }
        }
    }
}
 

Вам нужно прочитать весь ввод для каждого тестового примера, даже если количество ребер меньше n - 1 .