第 23 题
#include<bits/stdc++.h>
const int N=1e6+50;
int n, m, min[N],out[N],f[N],siz[N],ans;
struct edge
{
int u, v, w;
} e[N];
inline int find(int x)
{
while (x!=f[x])
x=f[x]=f[f[x]];
return x;
}
inline void merge(int x,int y)
{
if (siz[x]>siz[y]) std::swap(x,y);
f[x]=y;
}
int main()
{
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i)
{
f[i]=i,siz[i]=1;
}
for (int i=1; i<=m; ++i)
{
scanf ("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
}
int components=n;
while (components>1)
{
memset (min,0x3f,sizeof (min));
for (int i=1; i<=m; ++i)
{
int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
if (u!=v)
{
if (w<min[u]) min[u]=w,out[u]=v;
if (w<min[v]) min[v]=w,out[v]=u;
}
}
for (int i=1; i<=n; ++i)
{
int x=find(i) ;
if (out[x])
{
int y=find(out[x]);
if (x!=y)
{
merge(x,y);
--components;
ans+=min[x];
}
}
}
}
printf("%d",ans);
return 0;
}
提示:该程序的输入为一张n个点m条边的连通无向图。输入格式为:
输入的第一行包含两个整数 n,m(1≤n≤m≤100)。
接下来一行，包含三个整数u,v,w(1≤u,v≤n,1≤w≤100)。
判断题
第 23 题 (1分)该程序实现了用于求无向图G=(V,E)的最小生成树的算法。( )
第 24 题 (1分)程序中使用了邻接矩阵来存储图G=(V,E)。( )
第 25 题 为了确保该算法的结果符合预期输入需要保证所有的w互不相同。( )
第 26 题 对于任意合法的输入，该程序一定会在有限步内返回结果。( )
第 27 题 变量components在运行过程中可达到的最小值为( )。
第 28 题 该程序的时间复杂度为( ) 。