ACM 1233 还是畅通工程，我用的是并查集的思路，其中排序用的冒泡，提交显示超时，求指导，问题出在哪

ACM 1233 还是畅通工程，我用的是并查集的思路，其中排序用的冒泡，提交显示超时，求指导，问题出在哪

冒泡排序的时间复杂度是o(n^2)，但是这个n指的是待排序的元素数量，这题里输入的点数是n，边数是n(n-1)/2，也就是n^2级别的边数，你这里要排序的是边，所以你用冒泡的时间复杂度就是o((n^2)^2)=o(n^4)，这题n是100，n^4=10亿，一般OJ上1亿级别的复杂度就要跑接近1秒，你这单组数据就10亿，更别说题目还是多组数据，必然超时。这题要排序边的话必须要用o(nlogn)复杂度的排序，比如快速排序、堆排序和归并排序。
另外，除开排序，你这代码本身逻辑也有问题啊，你试一下这组数据：
4
1 2 1
1 3 7
1 4 8
2 3 9
2 4 7
3 4 1
答案应该是9。
你说用到并查集，我完全没看到并查集在哪里啊，这题就是个完全图的最小生成树，用prim算法会好一点，用kruskal算法的话并查集部分还要加上路径压缩才不会超时。你这里的town数组其实只有等于node和不等于node两种状态是有用的，node的值又不会变，这和boolean数组没什么实质的区别，这就是个标记数组，而不是并查集。

用冒泡是N^4的算法啊，明显超时好么追问不是n^2吗有哪个算法能提升很多吗追答怎么能是N^2，数据量是N^2，冒泡是数据量的平方，不就是N^4
快排就快的多了