判断最小生成树是否唯一

在最小生成树的推论中，生成树一定包含连接两个森林中间权值最小的边，所以在做最小生成树的同时统计这些备选边，若备选边大于所需的，则不唯一。

#include<bits/stdc++.h>
#define f(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
const int MAXN=200005;
struct Node{
int u,v,w;
bool operator < (const Node& tmp)const{
return w<tmp.w;
}
}a[MAXN];
int n,m,fa[MAXN];
inline void Makeset()
{
int i;
f(i,1,n) fa[i]=i;
}
inline int Find(int x)
{
return fa[x]==x?x:fa[x]=Find(fa[x]);
}
inline bool Union(int x,int y)
{
x=Find(x);y=Find(y);
if(x==y) return false;
fa[x]=y;
return true;
}
int main()
{
ios::sync_with_stdio(false);
int i,j,u,v,w;
int T;
cin>>T;
while(T--){
long long ans=0,num=0,cnt=0,pos=0;
cin>>n>>m;
Makeset();
f(i,1,m){
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+1+m);
f(i,1,m){
u=a[i].u;v=a[i].v;w=a[i].w;
if(pos<i){
pos=i;
while(pos+1<=m&&a[pos].w==a[pos+1].w) pos++;
f(j,i,pos){
if(Find(a[j].u)!=Find(a[j].v)) cnt++;
}
}
if(Union(u,v)){
num++;
ans+=w;
if(num==n-1) break;
}
}
cout<<ans<<endl;
if(cnt>n-1){
cout<<"No"<<endl;
}
else cout<<"Yes"<<endl;
}
return 0;
}

最后

以上就是义气大地为你收集整理的判断最小生成树是否唯一的全部内容，希望文章能够帮你解决判断最小生成树是否唯一所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。