作业让我们输入顶点数和无向图邻接矩阵得到MST的路径长，我用的kruskal。
简单的case我已经通过编译了，但是hard case我就过不了（比如1000个顶点的矩阵）
但我觉得我的已经很减时间复杂度了，大佬救急求助哇
#include<stdio.h>
#include<stdlib.h>
#define Max 1001
typedef struct{
int vex1;
int vex2;
int weight;
}Edge;
typedef struct{
int vex[Max];
Edge edge[Max];
int vexnum;
int edgenum;
}EdgeGraph;
int adjmatrix[1000][1000];
int parent[1000];
int rank[1000];
EdgeGraph G;
void init(int n)
{
for (int i = 0; i < n; ++i){
parent[i] = i;
rank[i] = 1;
}
}
int find(int i)
{
if (parent[i] == i)
return i;
else{
parent[i] = find(parent[i]);
return parent[i];
}
}
void Union(int x, int y)//通过秩的比较，进行路径压缩
{
if (x == y) return;
if (rank[x] < rank[y]) parent[x] = y;
if (rank[x] > rank[y]) parent[y] = x;
if (rank[x] == rank[y]){
rank[y]++;
parent[x] = y;
}
}
int main()
{
int i=0;
int result[500];
for(int j=0; j<Max; j++){
G.vex[j]=j;
}
int vertex=0;
scanf("%d",&vertex);
while(vertex!=0){
G.vexnum = vertex;
int num=0;
for( int m=0; m<vertex; m++){
for( int n=0; n<vertex; n++){
scanf("%d",&adjmatrix[m][n]);
if( m<n && adjmatrix[m][n]!=0 ){
G.edge[num].vex1=m;
G.edge[num].vex2=n;
G.edge[num].weight=adjmatrix[m][n];
num++;
}
}
}
G.edgenum = num;
Edge temp;
for( int n=0; n<num-1; n++){
for( int m=n+1; m<num; m++){
if( G.edge[n].weight > G.edge[m].weight ){
temp = G.edge[n];
G.edge[n] = G.edge[m];
G.edge[m] = temp;
}
}
}
int m;
int root1,root2;
int length=0;
for(int a=0; a<vertex; a++){
init(vertex);
}
for( m=0; m<G.edgenum; m++){
root1=find(G.edge[m].vex1);
root2=find(G.edge[m].vex2);
if( root1!=root2 ){
length += G.edge[m].weight;
Union(root1,root2);
}
}
result[i]=length;
i++;
scanf("%d",&vertex);
}
for(int a=0; a<i; a++){
printf("%d\n",result[a]);
}
return 0;
}

不要
单机贴吧

问题：
1. vex 意义不明
2. 楼主按秩合并乱写
3. init 已经有 for 使用时又套一层 而且最后一个点没改到
4. n^2 sort

https://pastebin.com/w6sLHY2j