给定一个 $n$ 个点 $m$ 条边的带边权无向图，对于每条边，判断其 一定/可能/一定不 在最小生成树中。

$n, m, w(\text{边权}) \leq 50000$

老师的做法

Kruskal 算法可以判断哪些边一定不在最小生成树中。

如果边权更小的边能使得一条边两端的点连通，这条边就一定不在。

如何区分是否一定在最小生成树中。

在每组边权中的割边。

我的做法

跑 Kruskal，每次把边权相同的边一起处理。对于这些边，分别计算出每个边两个端点所在的连通块（并查集），记为 $xf \leftrightarrow yf$。如果在这些边里，二元组（不分顺序） $xf \leftrightarrow yf$ 有重复，那就都标记为「有可能」；如果 $xf \leftrightarrow yf$ 没有重复，那么这条边就是「一定」；如果 $xf == yf$，就说明这条边「一定不」。

代码如下，A1、WA7、T2，我调了好久挑不出来，求助各位大佬麻烦帮帮忙，感激不尽。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>

using namespace std;

const int N = 5e4 + 10, M = 1e5 + 10;

int n, m;

struct edge{
	int u, v, w, id;
}e[M];
int ans[N]; // 0 -> 一定	1 -> 有可能		-1 -> 不可能

bool cmp(edge a, edge b){
	return a.w < b.w;
}

int fa[N];

int getfa(int x){
	if(fa[x] < 0){
		return x;
	}else{
		return fa[x] = getfa(fa[x]);
	}
}

int merge(int x, int y){
	fa[y] += fa[x];
	fa[x] = y;
}

map <pair<int, int>, int> mp;
int nxt;

int main(){
	
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
		e[i].id = i;
	}
	
	sort(e+1, e+m+1, cmp);
	memset(fa, -1, sizeof(fa));
	
	for(int i = 1; i <= m; i++){
		
		if(i > nxt){
			mp.clear();
			for(int j = i; j <= m; j++){
				if(e[j].w != e[i].w){
					nxt = j-1;
					break;
				}else{
					int xf = getfa(e[j].u), yf = getfa(e[j].v);
					if(xf != yf){
						if(xf > yf){
							swap(xf, yf);
						} 
						int qmp = mp[{xf, yf}];
						if(qmp > 0){
							ans[e[qmp].id] = 1;
							ans[e[j].id] = 1;
						}else{
							mp[{xf, yf}] = j;
						}
					}else{
						ans[e[j].id] = -1;
					}
				}
			}
		}
		
		int xf = getfa(e[i].u), yf = getfa(e[i].v);
		if(xf != yf){
			if(fa[xf] >= fa[yf]){
				merge(xf, yf);
			}else{
				merge(yf, xf);
			}
		}
		
	}
	
	for(int i = 1; i <= m; i++){
		switch(ans[i]){
			case 1:
				puts("at least one");
				break;
			case -1:
				puts("none");
				break;
			case 0:
				puts("any");
		}
	}
	
	
	return 0;
}

如果我的思路有戏，麻烦看看是哪里写挂了；如果假了，麻烦举出一个反例，或者说说为什么。再次感谢！