DirectedMST reconstruction crashes

[simonlindholm]

With https://github.com/bqi343/USACO/blob/master/Implementations/content/graphs%20(12)/Misc/DirectedMST.h,

int main() {
    int n = 4, r = 1;
    vector<tuple<int, int, int>> data = {
        {0, 3, 27},
        {1, 2, 32},
        {2, 3, 25},
        {3, 0, 31},
        {3, 2, 23},
    };
    vector<Edge> edges;
    trav(e, data) {
        int a = get<0>(e);
        int b = get<1>(e);
        int w = get<2>(e);
        edges.push_back({a, b, w});
    }

    dmst(n, r, edges);
}

ends up with inEdge.s == -1 in the restore loop, causing it to misbehave and in practice later hit this assert: assert(i == r ? in[i].s == -1 : in[i].s == i);.

Found while looking into importing it into KACTL, through the directed MST stress test: https://github.com/kth-competitive-programming/kactl/blob/master/stress-tests/graph/DirectedMST.cpp. I don't understand the restoration algorithm well enough to know how to patch it.

[bqi343]

Yeah I'm not sure if I totally understand it either but I'll look into it.

[bqi343]

Should be fixed now (was missing a dsu.get()). Thanks!

https://github.com/bqi343/USACO/blob/master/Implementations/content/graphs%20(12)/Misc/DirectedMST.cpp

[simonlindholm]

Sweet!

Also, I should ask, would you be fine with CC0-licensing the reconstruction and having it be part of upstream KACTL? (I code-golfed it a bit: https://github.com/kth-competitive-programming/kactl/compare/master...simonlindholm:dmst-reconstruction )

[bqi343]

yeah sure