判断MST是否唯一

53 阅读 0 评论 35 点赞

我是靠谱客的博主爱听歌导师，最近开发中收集的这篇文章主要介绍判断MST是否唯一，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
#include<stack>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>

#define ll __int64
#define lll unsigned long long
#define MAX 10009
#define eps 1e-8
#define INF 0xfffffff
#define mod 1000000007
#define MAXN 101 //顶点的最大个数
#define MAXM 10000 //边的最大个数

using namespace std;
/*
求MST是否唯一
1.对图中的每条边，是否有相同权值的边。如果有进行标记。
2.求MST
3.求MST之后，如果MST没有包含标记的边，则唯一，如果含有，依次删除标记的边，再求MST，看求得MST权值与原值相同则不唯一。
*/
struct edge
{
int x,y,z;
int equal;//标记用来是否与其他的权值相同，如果有为1，否则为0
int used;//在第一次求MST中，是否包含该边，1包含，0不包含
int del;//边是否删除，0表示删除，否则为1
} edges[MAXM];

bool cmp(edge x,edge y)
{
return x.z<y.z;
}

int N,M;//N个点，M条边
int father[MAX];
bool frist;//第一次求MST得标记

int Find(int x)
{
if (father[x]!=x)
father[x]=Find(father[x]);
return father[x];
}
void init()
{
for(int i = 0; i<=N; i++)
father[i] = i;
}
void Union(int x,int y)
{
int xx=Find(x);
int yy=Find(y);
if( xx == yy ) return ;
father[yy] = xx;
}
int Krusal()
{
int sum = 0,num = 0;//MST的权值，已用的边的数目
init();
for(int i = 0; i<M; i++)
{
if(edges[i].del==1)continue;//如果被删除，跳过该边
int xx = edges[i].x;
int yy = edges[i].y;
if(Find(xx)!=Find(yy))
{
sum+=edges[i].z;
num++;
Union(xx,yy);
if(frist) edges[i].used = 1;//如果为真值则是第一次求。
}
if(num>=N-1)break;
}
return sum;
}
int main()
{
int t;
int xx,yy,zz;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&N,&M);
for(int i = 0; i<M; i++)
{
scanf("%d%d%d",&xx,&yy,&zz);
edges[i].x = xx - 1;
edges[i].y = yy - 1;
edges[i].z = zz;
edges[i].equal = 0;
edges[i].del = 0;
edges[i].used = 0;
}
for(int i = 0; i<M; i++)
{
for(int j = 0; j<M; j++)
{
if(i==j)continue;
if(edges[i].z==edges[j].z)//标记是否有相同的权值的边
{
edges[j].equal = 1;
}
}
}
sort(edges,edges+M,cmp);
frist = 1;
int w1 = Krusal();
int w2;
int j;
frist = 0;
for( j = 0; j<M; j++)
{
if(edges[j].used&&edges[j].equal)//如果是第一次求得边并且是权值相同的边
{
edges[j].del = 1;
w2 = Krusal();
if(w1==w2)
{
puts("Not Unique!");
break;
}
}
}
if(j>=M)
{
printf("%dn",w1);
}
}
return 0;
}
/*
2
7 12
1 2 6
1 6 6
1 7 6
2 3 2
2 7 3
3 4 3
3 7 2
4 5 1
4 7 4
5 6 8
5 7 3
6 7 7
*/