Find edges that appear on every MST and find edges that appear in none of the MSTs.

main.cpp

#include <vector>
#include <iostream>
#include <fstream>

#define VERIFY

#ifdef VERIFY
#include <sstream>
#include <chrono>
#endif

#include "Solution.h"

void processFile(std::ifstream &ifs, std::ostream& os) {
    if(!ifs.is_open()) return;

    size_t V, E;
    ifs >> V >> E;
    std::vector<Edge> edges;
    for (size_t i = 0; i < E; i++) {
        size_t a, b, w;
        ifs >> a >> b >> w;
        edges.emplace_back(a - 1, b - 1, w);
    }
    ifs.close();

    Solution sol = solve(V, edges);
    os << sol.superLightEdges.size() << ' ' << sol.otherEdges.size() << '\n';
    for(const auto& edge: sol.superLightEdges) {
        os << edge.a + 1 << ' ' << edge.b + 1 << '\n';
    }
    for(const auto& edge: sol.otherEdges) {
        os << edge.a + 1 << ' ' << edge.b + 1 << '\n';
    }
}

int main() {
#ifdef VERIFY
    auto begin = std::chrono::steady_clock::now();
    for (size_t i = 0; i < 24; i++) {
        std::ostringstream ossi;
        std::ostringstream osso;
        ossi << "private_tests/scurt/input/test" << i << ".in";
        osso << "private_tests/scurt/out/test" << i << ".out";
        std::ifstream ifs(ossi.str());

        std::ofstream ofs(osso.str());
//        std::ostream& ofs = std::cout;
        processFile(ifs, ofs);
    }
    auto end = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() * 1e-6 << " sec\n";
#else
    std::ifstream ifs("scurt.in");
    std::ofstream ofs("scurt.out");
    processFile(ifs, ofs);
#endif
    return 0;
}

scurt.in

10 20
8 9 5
3 10 2
3 6 8
4 5 7
6 10 9
1 6 5
5 9 1
4 9 6
2 9 7
3 4 9
2 5 2
2 10 3
6 8 7
6 9 8
2 7 3
5 7 4
2 6 7
3 5 2
3 8 9
4 8 6

Solution.h

#pragma once

#include <vector>
#include <map>
#include <unordered_set>

template<typename T>
struct AdjM {
    std::vector<T> mat;
    size_t V;

    explicit AdjM(size_t V)
            : V(V), mat(V * V, static_cast<T>(0)) {
    }

    void addEdge(size_t i, size_t j, T w) {
        mat[i * V + j] = w;
        mat[j * V + i] = w;
    }

    T& get(size_t i, size_t j) {
        return mat[i * V + j];
    }

    const T &get(size_t i, size_t j) const {
        return mat[i * V + j];
    }
};

struct Edge {
    size_t a, b;
    size_t w;

    Edge(size_t a, size_t b, size_t w) : a(a), b(b), w(w) {}
};

enum class EdgeStatus {
    Other = 0,
    SuperLight,
    SuperHeavy,
};

struct Solution {
    std::vector<Edge> superLightEdges;
    std::vector<Edge> otherEdges;

    Solution() : superLightEdges(), otherEdges() {}
};

struct Graph {
    size_t V, E;
    AdjM<size_t> adjM;
    std::vector<std::vector<size_t>> adjL;

    explicit Graph(size_t V)
            : V(V), E(0), adjM(V), adjL(V, std::vector<size_t>()) {}

    void addEdge(const Edge &edge) {
        E += 1;
        adjM.addEdge(edge.a, edge.b, edge.w);
        adjL[edge.a].push_back(edge.b);
        adjL[edge.b].push_back(edge.a);
    }
};

struct PairHash {
    template<class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return std::hash<T1>{}(p.first) ^ std::hash<T2>{}(p.second);
    }
};

struct BridgeProcessor {
    std::vector<int> pre;
    std::vector<int> low;
    size_t V;
    size_t t;
    std::unordered_set<std::pair<size_t, size_t>, PairHash> edges;

    explicit BridgeProcessor(const Graph &g)
            : pre(g.V, -1), low(g.V, -1), V(g.V), t(0), edges() {
        for (size_t v = 0; v < V; v++) {
            if (pre[v] == -1) {
                dfs(g, v, v);
            }
        }
    }

    void dfs(const Graph &g, size_t u, size_t v) {
        pre[v] = t++;
        low[v] = pre[v];
        for (const auto &w: g.adjL[v]) {
            if (pre[w] == -1) {
                dfs(g, v, w);
                low[v] = std::min(low[v], low[w]);
                if (low[w] == pre[w]) {
                    edges.emplace(v, w);
                    edges.emplace(w, v);
                }
            } else if (w != u) {
                low[v] = std::min(low[v], pre[w]);
            }
        }
    }

    bool findBridge(const Edge &edge) {
        return edges.end() != edges.find(std::make_pair(edge.a, edge.b));
    }
};

struct SubSet {
    size_t parent;
    size_t rank;
};

size_t find(std::vector<SubSet> &subsets, size_t i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

void unify(std::vector<SubSet> &subsets, size_t a, size_t b) {
    size_t aroot = find(subsets, a);
    size_t broot = find(subsets, b);
    if (subsets[aroot].rank < subsets[broot].rank) {
        subsets[aroot].parent = broot;
    } else if (subsets[aroot].rank > subsets[broot].rank) {
        subsets[broot].parent = aroot;
    } else {
        subsets[aroot].parent = broot;
        subsets[broot].rank++;
    }
}

Solution solve(size_t V, const std::vector<Edge> &edges) {
    AdjM<EdgeStatus> stats(V);

    Graph g(V);
    for (const auto &edge : edges) {
        g.addEdge(edge);
    }

    std::map<size_t, std::vector<const Edge *>> edgeGroups;
    for (const auto &edge : edges) {
        edgeGroups[edge.w].push_back(&edge);
    }

    Graph h(V);
    std::vector<SubSet> subsets(V);
    for (size_t i = 0; i < V; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }
    for (auto p = edgeGroups.cbegin(), q = edgeGroups.cend(); p != q; ++p) {
        const auto &w1 = p->first;
        const auto &edgeGroup1 = p->second;
        for (const auto &edgep : edgeGroup1) {
            h.addEdge(*edgep);
            size_t aset = find(subsets, edgep->a);
            size_t bset = find(subsets, edgep->b);
            unify(subsets, aset, bset); // union
        }
        BridgeProcessor bridgeProcessor(h);
        for (const auto &edgep: edgeGroup1) {
            if (bridgeProcessor.findBridge(*edgep)) {
                stats.addEdge(edgep->a, edgep->b, EdgeStatus::SuperLight);
            }
        }
        const auto& r = std::next(p, 1);
        if(r != q) {
            const auto &edgeGroup2 = r->second;
            for (const auto &edgep : edgeGroup2) {
                size_t aset = find(subsets, edgep->a);
                size_t bset = find(subsets, edgep->b);
                if (aset == bset) { // in a cycle
                    stats.addEdge(edgep->a, edgep->b, EdgeStatus::SuperHeavy);
                }
            }
        }
    }

    Solution sol;
    for (const auto &edge : edges) {
        EdgeStatus status = stats.get(edge.a, edge.b);
        if (status == EdgeStatus::SuperLight) {
            sol.superLightEdges.push_back(edge);
        } else if (status == EdgeStatus::Other) {
            sol.otherEdges.push_back(edge);
        }
    }
    return sol;
}