160D - Edges in MST - CodeForces Solution

#include <bits/stdc++.h>
#define inf 1e18
#define pll pair<ll,ll>
#define pb push_back
#define fi first 
#define se second
/* target VOI 2025 */
 
using namespace std;
typedef long long int lli;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll N = 1e5 * 2 + 10;
const ll maxn = 1e7;
ll num[N], low[N];
ll ans[N]; 
ll par[N];
vector<pll>adj[N];
ll cnt = 0;
/*
nhap idea : 
- sort edge theo length
- khi do, tuong tuong co 1 nhom canh ket noi 2 thanh phan lien thong 
co cung do dai. The thi cno se replace thay nhau tao ra mst. 
- Vay cac canh do co the la at least 1 hoac any
- Vay thi ta chia ra 3 case
- Canh khong thuoc mst nao khi no ket noi 2 tplt da duoc lien ket tu 
truoc
- Canh thuoc tat ca mst se la canh cau cua graph
*/
// ki hieu : 0 la none, 1 la some, 2 la any
ll find(ll v){
    if(v == par[v]) return v;
    else return par[v] = find(par[v]);
}
bool join(ll u, ll v){
    u = find(u); v = find(v);
    if(u == v) return false;
    par[v] = u;
    return true;
}
struct node{
    ll u,v,c,id;
};
bool cmp(node a, node b){
    return a.c < b.c;
}
void dfs(ll u, ll par){
    num[u] = low[u] = ++cnt;
    for(auto &v : adj[u]){
        if(v.se == par) continue;
        if(num[v.fi]){
            low[u] = min(low[u], num[v.fi]);
        }
        else{
            dfs(v.fi, v.se);
            low[u] = min(low[u], low[v.fi]);
            if(low[v.fi] == num[v.fi]){
                ans[v.se] = 2; 
            }
        }
    }
}   
vector<node>e;
void process(vector<node>&pre){
    if(pre.empty()) return;
    for(int i = 0; i < pre.size();i++){
        pre[i].u = find(pre[i].u);
        pre[i].v = find(pre[i].v);
        adj[pre[i].u].clear();
        adj[pre[i].v].clear();
        num[pre[i].u] = num[pre[i].v] = 0;
    }
    for(int i = 0; i < pre.size();i++){
        if(pre[i].u != pre[i].v){
            ans[pre[i].id] = 1;
            adj[pre[i].u].pb({pre[i].v, pre[i].id});
            adj[pre[i].v].pb({pre[i].u, pre[i].id});
        }
        else{
            ans[pre[i].id] = 0;
        }
    }
    for(auto &i : pre){
        if(!num[i.u]) dfs(i.u, -1);
    }
    for(auto &x : pre){
        join(x.u, x.v);
    }
}   
void solve(){
    vector<node>pre;
    ll n,m; cin >> n >> m;
    for(int i = 1; i <= n;i++){
        par[i] = i;
    }
    for(int i = 1; i <= m;i++){
        ll u,v,c; cin >> u >> v >> c;
        e.pb({u,v,c,i});
    }
    sort(e.begin(), e.end(), cmp);
    for(auto &x : e){
        if(!pre.empty() && pre.back().c == x.c){
            pre.pb(x);
        }
        else{
            process(pre);
            pre.clear();
            pre.pb(x);
        }
    }
    process(pre);
    for(int i = 1; i <= m;i++){
        if(ans[i] == 0){
            cout << "none" << "\n";
        }
        else if(ans[i] == 1){
            cout << "at least one" << "\n";
        } 
        else if(ans[i] == 2) cout << "any" << "\n";
    }
}
 
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    solve();
}