Editorial for Road Roles

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Sort edges by weight and process equal-weight batches, as in Kruskal.

Before handling weight w, the DSU holds the forest built from edges of weight strictly less than w. For each edge e = (u, v) of weight w:

  • if u and v are already in the same component, e is useless;
  • otherwise e can appear in some MST.

Among the non-useless weight-w edges, contract each current DSU component to a vertex and build the multigraph of those edges. In that multigraph:

  • bridges are forced (they are the unique lightest connection across their cut);
  • non-bridges are optional.

Finally unite all non-useless edges of this weight and continue.

Finding bridges over all batches is linear in the number of candidate edges after sorting, so the whole algorithm is O(m \log m).

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w, idx;
};

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] > sz[b]) swap(a, b);
        p[a] = b;
        sz[b] += sz[a];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c, i};
    }

    sort(edges.begin(), edges.end(), [](const Edge& x, const Edge& y) {
        return x.w < y.w;
    });

    DSU dsu(n + 1);
    vector<string> ans(m);

    for (int i = 0; i < m; ) {
        int j = i;
        while (j < m && edges[j].w == edges[i].w) j++;

        vector<Edge> cand;
        for (int t = i; t < j; t++) {
            auto e = edges[t];
            if (dsu.find(e.u) == dsu.find(e.v)) {
                ans[e.idx] = "useless";
            } else {
                cand.push_back(e);
            }
        }

        vector<int> nodes;
        for (auto& e : cand) {
            nodes.push_back(dsu.find(e.u));
            nodes.push_back(dsu.find(e.v));
        }
        sort(nodes.begin(), nodes.end());
        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
        auto id_of = [&](int x) {
            return int(lower_bound(nodes.begin(), nodes.end(), x) - nodes.begin());
        };

        int N = (int)nodes.size();
        vector<vector<pair<int, int>>> g(N);
        for (int t = 0; t < (int)cand.size(); t++) {
            int u = id_of(dsu.find(cand[t].u));
            int v = id_of(dsu.find(cand[t].v));
            g[u].push_back({v, t});
            g[v].push_back({u, t});
        }

        vector<int> disc(N, -1), low(N, 0), parent_edge(N, -1);
        vector<char> is_bridge(cand.size(), 0);
        int timer = 0;

        for (int start = 0; start < N; start++) {
            if (disc[start] != -1) continue;
            vector<pair<int, int>> st;
            disc[start] = low[start] = timer++;
            st.push_back({start, 0});
            while (!st.empty()) {
                auto& [v, ei] = st.back();
                if (ei == (int)g[v].size()) {
                    st.pop_back();
                    if (!st.empty()) {
                        int p = st.back().first;
                        low[p] = min(low[p], low[v]);
                        if (low[v] > disc[p]) is_bridge[parent_edge[v]] = 1;
                    }
                    continue;
                }
                auto [to, eid] = g[v][ei++];
                if (eid == parent_edge[v]) continue;
                if (disc[to] != -1) {
                    low[v] = min(low[v], disc[to]);
                } else {
                    parent_edge[to] = eid;
                    disc[to] = low[to] = timer++;
                    st.push_back({to, 0});
                }
            }
        }

        for (int t = 0; t < (int)cand.size(); t++) {
            ans[cand[t].idx] = is_bridge[t] ? "forced" : "optional";
        }

        for (auto& e : cand) dsu.unite(e.u, e.v);
        i = j;
    }

    for (auto& s : ans) cout << s << "\n";
    return 0;
}

Comments

There are no comments at the moment.