POJ 1679 判断无向图最小生成树是否唯一 Kruskal算法
题目链接
思想：Kruskal算法思想：把所有的边升序排序，每次加一条边，加的时候判断一下当前边所连接的两个顶点是否已经连通（并查集），是则舍弃，否则 要这条边并且更新一下并查集的head数组。
【POJ 1679 判断无向图最小生成树是否唯一 Kruskal算法】如果最小生成树不唯一，那么权值相同的边肯定有多条。
每次在加边的时候，判断和在整个图中和这条边权值相等且能加入到最小生成树的边有几条（设为sum1）（每次判断不更新并查集head数组），然后将这些权值相等的边依次加入到树中（更新head数组），如果此时能加入的边（sum2),有sum1>sum2，说明最小生成树不唯一。
# include
# include
# include
# include
using namespace std;
# define MAX 0x3f3f3f3f
# define MAXN 110
# define MAXM 11000
int N, M;
int head[MAXN];
///并查集记录父节点数组
int ans;
struct node
{
int s, e;
int price;
} z[MAXM];
///存边
bool cmp(struct node A, struct node B)
{
return A.pricesum2)
return false;
}
return true;
}
int main()
{
int T;
while(cin>>T)
{
while(T--)
{
cin>>N>>M;
Init();
for(int i=0;
i>a>>b>>c;
z[i]=(node)
{
a,b,c
};
}
int flag=Kruskal();
if(!flag)
cout<<"Not Unique!"< 推荐阅读
- C语言解方程的根和判断是否是闰年
- 对今年以来股市的看法及后期判断
- vue中的条件判断详解v-if|vue中的条件判断详解v-if v-else v-else-if v-show
- Java应该在哪里判断List是否为空
- JavaScript判断数组的方法总结与推荐
- 给老板选择题而不是问答题或判断题
- 判断scroll向上还是向下
- 南红手串的品质如何判断（）
- python-Flask（jinja2）语法（判断与循环）
- 如何判断体内是否有湿气（）