lessons/参考实现/06-最小与最大生成树/CodeForces-160D.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct DSU {
    vector<int> p, s;
    explicit DSU(int n) : p(n), s(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 (s[a] < s[b]) swap(a, b); p[b] = a; s[a] += s[b];
    }
};
struct Edge { int u, v, w, id; };

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) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        --edges[i].u; --edges[i].v; edges[i].id = i;
    }
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; });
    vector<string> answer(m, "none"); DSU dsu(n);
    for (int left = 0; left < m; ) {
        int right = left;
        while (right < m && edges[right].w == edges[left].w) ++right;
        vector<int> candidate, roots;
        for (int i = left; i < right; ++i) {
            int a = dsu.find(edges[i].u), b = dsu.find(edges[i].v);
            if (a != b) {
                candidate.push_back(i); roots.push_back(a); roots.push_back(b);
                answer[edges[i].id] = "at least one";
            }
        }
        sort(roots.begin(), roots.end()); roots.erase(unique(roots.begin(), roots.end()), roots.end());
        vector<vector<pair<int, int>>> graph(roots.size());
        for (int index : candidate) {
            int a = int(lower_bound(roots.begin(), roots.end(), dsu.find(edges[index].u)) - roots.begin());
            int b = int(lower_bound(roots.begin(), roots.end(), dsu.find(edges[index].v)) - roots.begin());
            graph[a].push_back({b, edges[index].id}); graph[b].push_back({a, edges[index].id});
        }
        vector<int> tin(roots.size(), -1), low(roots.size()); int timer = 0;
        function<void(int, int)> dfs = [&](int u, int parent_edge) {
            tin[u] = low[u] = timer++;
            for (auto [v, id] : graph[u]) {
                if (id == parent_edge) continue;
                if (tin[v] == -1) {
                    dfs(v, id); low[u] = min(low[u], low[v]);
                    if (low[v] > tin[u]) answer[id] = "any";
                } else low[u] = min(low[u], tin[v]);
            }
        };
        for (int v = 0; v < static_cast<int>(roots.size()); ++v) if (tin[v] == -1) dfs(v, -1);
        for (int i = left; i < right; ++i) dsu.unite(edges[i].u, edges[i].v);
        left = right;
    }
    for (const string &s : answer) cout << s << '\n';
}