先来看一个例题：Forsaken喜欢独一无二的树

题意：
现在给定一个 $n$ 个点，$m$ 条边的图，每条边 $e_i$ 都有一个权值 $w_i$ 。

刚开始最小生成树可能不唯一，现在可以删除一些边，使得剩下的边的最小生成树大小不变并且唯一。

求删除的边的权值和最小是多少?

分析：
什么样的边会影响到最小生成树的唯一性呢？

kruskal 求最小生成树 是将所有边权从小到大排序，然后判断当前边的两个端点所在连通块是否连通。如果没有连通，那么这条边就需要拿。
而此时如果有另外一条边，虽然也可以将这两个连通块合并，但是其权值比较大，那么这条边是不会影响到最小生成树的。
所以，只有两个边的权值相同，并且都能将端点的两个连通块合并，这么这两个边选择哪个都行，那么最小生成树就不唯一了。

所以，为了保证最小生成树唯一，那么就是要去掉若干条 权值相同并且能够合并相同连通块的边，只剩一个这样的边就行。

如何实现呢？

我们像 kruskal 一样将所有的边按照权值排序，从小到大遍历所有的边。
对于当前边来说，将所有的和当前边权相等的边都拿过来（双指针）。对于这些权值相同的边，我们要去掉一些能够合并相同连通块的边。

我们可以先将所有的权值相同且能够合并连通块的边都删除，然后再留下最小生成树中的边。
这样，对于权值相同的能够合并连通块的多余边就被删除了。

• 先遍历所有边，判断其是否可选，也就是判断其端点连接的两个连通块是否已经连通。如果没有连通，说明可选，删除的权值和 ans += wi；
  这时，我们把能够合并连通块的所有边都删除了。
• 然后，再遍历一遍，用这些边求最小生成树权值和 sum。

最终，删除的多余边权之和就为 ans - sum。

	int sum = 0;
	for(int i=1;i<=m;i++)
	{
		int r = i;
		
		while(r <= m && a[r].w == a[i].w) r++;
		r--;
		
		for(int j=i;j<=r;j++)
		{
			int x = a[j].x, y = a[j].y, w = a[j].w;
			if(find(x) != find(y)) ans += w;
		}
		
		for(int j=i;j<=r;j++)
		{
			int x = a[j].x, y = a[j].y, w = a[j].w;
			if(find(x) != find(y)) pre[find(x)] = find(y), sum += w;
		}
		
		i = r;
	}
	
	ans -= sum;

完整Code：

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
map<PII,int> mp;

/**/

const int N = 200010, mod = 1e9+7;
int T, n, m;
struct node{
	int x, y, w;
}a[N];
int ans, pre[N];

bool cmp(node a, node b){
	return a.w < b.w;
}

int find(int x){
	if(pre[x] != x) pre[x] = find(pre[x]);
	return pre[x];
}

void kruskal()
{
	sort(a+1, a+m+1, cmp);
	
	int sum = 0;
	for(int i=1;i<=m;i++)
	{
		int r = i;
		
		while(r <= m && a[r].w == a[i].w) r++;
		r--;
		
		for(int j=i;j<=r;j++)
		{
			int x = a[j].x, y = a[j].y, w = a[j].w;
			if(find(x) != find(y)) ans += w; //能拿的都删去
		}
		
		for(int j=i;j<=r;j++)
		{
			int x = a[j].x, y = a[j].y, w = a[j].w;
			if(find(x) != find(y)) pre[find(x)] = find(y), sum += w; //求最小生成树
		}
		
		i = r;
	}
	
	ans -= sum; //把最小生成树的权值留下，删去的就是多余的了
}

signed main(){
	Ios;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++) pre[i] = i;
	
	for(int i=1;i<=m;i++)
	{
		int x, y, w;cin>>x>>y>>w;
		a[i] = {x, y, w};
	}
	
	kruskal();
	
	cout << ans;
	
	return 0;
}

这样，阻碍最小生成树唯一的边就都被删去了。

那么，如果需要判断一个图中最小生成树是否唯一，那么就可以用这种方法，看最终的删去边的权值是否为0，如果为0就是唯一的。
或者，也可以对于每一种权值来说，判断这其中的 可拿的边（端点所在连通块不连通） 是不是都在最小生成树中，如果有的不在，则说明最小生成树不唯一。

因为既然一个边可拿，也就是端点所在连通块不连通，那么其就应该出现在最小生成树中。而现在第二遍遍历跑最小生成树之后，发现之前可拿边的个数和可拿边的个数不同，那么也就是有多余的边，最小生成树不唯一。

例题：The Unique MST

Code：

#include<iostream>
#include<algorithm>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

/**/

const int N = 200010, mod = 1e9+7;
int T, n, m;
struct node{
	int x, y, w;
}a[N];
int ans, pre[N];
int sum;

bool cmp(node a, node b){
	return a.w < b.w;
}

int find(int x){
	if(pre[x] != x) pre[x] = find(pre[x]);
	return pre[x];
}

int kruskal()
{
	sort(a+1, a+m+1, cmp);
	
	for(int i=1;i<=m;i++)
	{
		int r = i;
		
		while(r <= m && a[r].w == a[i].w) r++;
		r--;
		
		int cnt = 0; //记录可拿边的个数 
		for(int j=i;j<=r;j++)
		{
			int x = a[j].x, y = a[j].y, w = a[j].w;
			if(find(x) != find(y)) cnt++; //可拿边个数++ 
		}
		
		for(int j=i;j<=r;j++)
		{
			int x = a[j].x, y = a[j].y, w = a[j].w;
			if(find(x) != find(y)) pre[find(x)] = find(y), sum += w, cnt --; //用掉了，cnt-- 
		}
		
		i = r;
		
		if(cnt) return 0; //最后还剩余可拿边，最小生成树不唯一 
	}
	return 1;
}

signed main(){
	Ios;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		
		ans = 0, sum = 0;
		for(int i=1;i<=n;i++) pre[i] = i;
		
		for(int i=1;i<=m;i++)
		{
			int x, y, w;cin>>x>>y>>w;
			a[i] = {x, y, w};
		}
		
		if(!kruskal()) cout<<"Not Unique!\n";
		else cout << sum <<endl;
	}
	
	return 0;
}

这种做法时间复杂度和求最小生成树复杂度相同，O(n+m)。
感觉比求次小生成树简单呢~

给定一个带权无向图，如果是连通图，则至少存在一棵最小生成树，有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重，并且判断其是否唯一。

输入格式：

首先第一行给出两个整数：无向图中顶点数 N（≤500）和边数 M。随后 M 行，每行给出一条边的两个端点和权重，格式为“顶点1 顶点2 权重”，其中顶点从 1 到N 编号，权重为正整数。题目保证最小生成树的总权重不会超过 230。

输出格式：

如果存在最小生成树，首先在第一行输出其总权重，第二行输出“Yes”，如果此树唯一，否则输出“No”。如果树不存在，则首先在第一行输出“No MST”，第二行输出图的连通集个数。

输入样例 1：

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5

结尾无空行

输出样例 1：

11
Yes

结尾无空行

输入样例 2：

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

结尾无空行

输出样例 2：

4
No

结尾无空行

输入样例 3：

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

结尾无空行

输出样例 3：

No MST
2

 问题1:是否能生成最小生成树？

——>根据kruskral算法，若合并次数< n - 1次，则说明无法生成。

问题2:不能生成最小生成树情况下有多少个连通集合？

——>用一个map存一下祖宗节点，最后输出size即可。

问题3:如何判断最小生成树是否唯一？

——>去求次小生成树，次小生成树和最小生成树只有一边之差。

         在求解最小生成树的过程中，我们用一个数组记录哪些边被用到了

         对于没有用到的边，它连接的两个顶点称作a, b。我们把这条没被用过的边加入到最小生成树中，并删除原最小生成树连接a，b的边，其实就是结果减去原连接a，b两点的边的长度，再加上新加的这条边的长度，去判断一下两种情况下结果是否相等， 如果相等就说明最小生成树不唯一（因为用到的边不同）。

上代码！

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>

using namespace std;

const int N = 510;
unordered_map<int, int> fa;
int n, m;
int p[N];

struct Edge
{
    int a, b, c;
    bool operator < (const Edge &w) const
    {
        return c < w.c;
    }
}edge[N * N];

bool st[N]; //判断边是否被用到了
int g[N];

int find(int x)//并查集+路径压缩
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }
    sort(edge, edge + m);
    int cnt = 0; //记录合并次数
    long long res = 0; //记录结果
    for(int i = 1; i <= n; i++) p[i] = i; //并查集初始化
    
    for(int i = 0; i < m; i++)
    {
        auto t = edge[i];
        int x = find(t.a), y = find(t.b);
        if(x != y) //集合不一样就合并
        {
            cnt++; //合并次数++
            st[i] = true; //边被使用了
            p[x] = y; //合并集合
            res += t.c;
            g[t.a] = g[t.b] = t.c; //记录边长，为后面判断生成树是否唯一服务
        }
    }
    
    if(cnt < n - 1) //合并次数 < n - 1说明不连通。（一开始1个点，一直加入加入...到n个点需要n - 1次）
    {
        for(int i = 1; i <= n; i++)
        {
            int t = find(i);
            if(!fa[t]) fa[t] = 1; //统计祖宗，放入map
        }
        cout << "No MST" << endl;
        cout << fa.size() << endl;//祖宗个数
        return 0;
    }
    cout << res << endl;
    for(int i = 0; i < n; i++)
    {
        if(!st[i]) // 边没用过
        {
            auto t = edge[i];
            int a = t.a, b = t.b; //边连的两个点
            if(res - g[a] + t.c == res) //结果相同则生成树不唯一
            {
                puts("No");
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

给定一个带权无向图，如果是连通图，则至少存在一棵最小生成树，有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重，并且判断其是否唯一。

输入格式：

首先第一行给出两个整数：无向图中顶点数 $N$（≤）和边数 $M$。随后 $M$ 行，每行给出一条边的两个端点和权重，格式为“顶点1 顶点2 权重”，其中顶点从 1 到$N$ 编号，权重为正整数。题目保证最小生成树的总权重不会超过 2​30​​。

输出格式：

如果存在最小生成树，首先在第一行输出其总权重，第二行输出“Yes”，如果此树唯一，否则输出“No”。如果树不存在，则首先在第一行输出“No MST”，第二行输出图的连通集个数。

输入样例 1：

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5

输出样例 1：

11
Yes

输入样例 2：

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

输出样例 2：

4
No

输入样例 3：

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

输出样例 3：

No MST
2

思路：我们可能先判断连通性，由于结点数比较少，可以通过dfs直接判断连通块的个数，对于最小生成树的唯一性，我们可以通过求出次小生成的权值，在于最小生成树的权值进行比较即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
const int maxn=550;

int vis[maxn];
const long long int inf=0x3f3f3f3f3f3f3f;
int G[maxn][maxn];
vector<int> v[maxn];
int fa[maxn];
long long int dis[maxn];
long long int pa[maxn][maxn];
bool used[maxn][maxn];
int n,m;
void dfs(int x)
{
    if(vis[x]) return ;
    vis[x]=1;
    for(int i=0; i<v[x].size(); i++)
    {
        dfs(v[x][i]);
    }
}
long long int prim(int x)
{
    memset(fa,0,sizeof(fa));
    memset(vis,0,sizeof(vis));
    memset(pa,0,sizeof(pa));
    memset(used,false,sizeof(used));
    for(int i=1; i<=n; i++)
    {
        dis[i]=G[x][i];
        fa[i]=x;
    }
    vis[x]=1;
    long long int ans=0;

    int cnt=0;
    int idx=x;
    for(int ka=1; ka<=n-1; ka++)
    {
        long long int maxx=inf;
        idx=0;
        for(int i=1; i<=n; i++)
        {
            if(!vis[i]&&dis[i]<maxx)
            {
                maxx=dis[i];
                idx=i;
            }
        }
        ans+=dis[idx];
        vis[idx]=1;
        used[idx][fa[idx]]=used[fa[idx]][idx]=1;
        for(int i=1; i<=n; i++)
        {
            if(vis[i]&&i!=idx )
            {
                pa[idx][i]=pa[i][idx]=max(dis[idx],pa[i][fa[idx]]);
            }
            else
            {
                if(dis[i]>G[idx][i])
                {
                    fa[i]=idx;
                    dis[i]=G[idx][i];
                }
            }
        }
    }
    return ans;
}
long long int second_tree(long long int t)
{
    long long int ans=inf;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i!=j&&used[i][j]==0)
                ans=min(ans,t+G[i][j]-pa[i][j]);
        }
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    memset(vis,0,sizeof(vis));
    memset(G,inf,sizeof(G));

    for(int i=0; i<m; i++)
    {
        int x,y,d;
        cin>>x>>y>>d;
        G[x][y]=G[y][x]=d;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]) continue;
        cnt++;
        dfs(i);
    }
    if(cnt>1)
    {
        cout<<"No MST"<<endl;
        cout<<cnt<<endl;
        return 0;
    }
    long long int tree=prim(1);
    long long int t2=second_tree(tree);
    cout<<tree<<endl;
    if(t2!=tree) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}