Editorial for Road Roles

Use this editorial only when stuck, and do not 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++)

Code 1

#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;
}

Comments0

No comments yet

Be the first to comment.

Editorial for Road Roles

Approach

Solution (C++)

Comments0

New comment