Codeforces 166(#111 Div2 only) D. Edges in MST

問題

n頂点m本の辺からなる重み付き無向グラフが与えられる。
m本の辺それぞれについて、

のいずれかを判別せよ。

制約条件

n, m≦10^5

方針

辺の重みが全部1である場合を考えると、
グラフの橋(取り除くとグラフが非連結になる辺)が必ず必要な辺。
残りの辺は含まれても含まれなくてもよい。


辺に重みがある場合も大体同じで、辺をコストの小さい順にソートして、
クラスカル法をしながら同じコストの辺をまとめて処理する。


今コストcの辺を処理しているとすると、クラスカル法で
コストc未満の辺が結ぶ頂点はマージされている。
連結成分を一つの頂点とみてグラフを作ると、重みなしの場合に帰着できる。
(ただし、同一連結成分を結ぶ辺は、"使わない辺になる")

ソースコード

spaghetti sourceの橋は、(a, b)に2本辺があったときに(a, b)をループとしてくれないので、回避するためにちょっと変な実装をした。
(同じ辺(a, b)が2本あったら橋でなくしただけ)

const char *str[] = {"none", "any", "at least one"};
const int MX = 100000;
int n, m, ans[MX];

int p[MX];
inline int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
inline void merge(int a, int b){
	a = root(a); b = root(b);
	if(a != b) p[b] = a;
}

int main(){
	scanf("%d%d", &n, &m);
	
	vector<pair<pi, pi> > es;
	rep(i, m){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		es.pb(mp(mp(c, i), mp(a - 1, b - 1)));
		
		ans[i] = 2;
	}
	rep(i, n) p[i] = i;
	
	#define F first
	#define S second
	
	sort(all(es));
	rep(i, m){
		
		int cnt = 0;
		vector<pair<int, pi> > e;
		vi v;
		for(int j = i; j < m && es[i].F.F == es[j].F.F; j++){
			
			int a = es[j].S.F, b = es[j].S.S;
			a = root(a); b = root(b);
			cnt++;
			
			if(a == b) ans[es[j].F.S] = 0;
			else{
				e.pb(mp(es[j].F.S, mp(a, b)));
				v.pb(a); v.pb(b);
			}
		}
		sort(all(v));
		v.erase(unique(all(v)), v.end());
		
		Graph g(v.size());
		map<pi, int> id;
		Edges bs;
		vector<vi> tmp;
		
		rep(j, e.size()){
			
			int a = lower_bound(all(v), e[j].S.F) - v.begin();
			int b = lower_bound(all(v), e[j].S.S) - v.begin();
			g[a].pb(Edge(a, b, 0));
			g[b].pb(Edge(b, a, 0));
			merge(e[j].S.F, e[j].S.S);
			
			if(id.count(mp(a, b))) id[mp(a, b)] = id[mp(b, a)] = -1;
			else id[mp(a, b)] = id[mp(b, a)] = e[j].F;
		}
		bridge(g, bs, tmp);
		
		
		rep(j, bs.size()){
			int a = bs[j].src, b = bs[j].dst;
			if(id[mp(a, b)] >= 0) ans[id[mp(a, b)]] = 1;
		}
		i += cnt - 1;
	}
	
	rep(i, m) puts(str[ans[i]]);
	return 0;
}