判断MST的唯一性
用kruskal算法实现，主要利用MST的环性质
- 先保存所有的边在一个边集数组a中，然后单独去构建一个MST，在a中没能用上的非安全边全部放到另一个边集数组b中
- 另外在构建MST过程要构建一个邻接表，用vextor来实现，也就是只统计MST之间的连通情况，非安全边的不统计在内
例如 1 2 3（安全边）
1 3 4（非安全边）
那么邻接表中，与点1相通的点有点2但是没有点3，因为点3不在MST中，所以在MST中遍历的时候是没办法直接从点1到点3的
- 接下来是就利用MST的环性质，一个MST中不管加入那条非安全边都将会形成一个环。所以我们枚举所有的非安全边，一条非安全边e，（u，v）权值为w，我们从一个顶点u出发去dfs，直到找到另一个顶点v为止。这样我们其实就是找到了这个环，然后原路返回，在返回的过程中查看这个环是否存在一条边的权值是否和e的权值w相同，若存在，我们其实是可以用e去替换这条边的，说明这个MST不是唯一
- 所以我们枚举所有的非安全边，若所以的非安全边都不能在它们形成的环中找到可以替代的边，那个这个MST就是唯一的
- 关键是dfs函数的写法，我们设置一个全局变量FIND，FIND=0表示没能找到替换的边，FIND=1表示找到了。dfs有返回值，返回0表示走到了某条路径走到了尽头但是都没有找到点v，要继续找，若是返回1，则说明已经找到了点v，同样是返回，但是这个返回的路径其实就是环的路径，所以没返回到一层就看看当前的边的权值和e的权值是否相同，并随时更改FIND。所以在dfs递归函数的出口处要做判断，最优先的判断是FIND，若FIND=1，那么说明不仅是找到了点v还找到了替换边，那么直接返回。次优先的判断是看dfs的返回值，若是0还要在当前层里面枚举，若不是只需要判断权值就可以返回了
l 说一下WA的地方。其一是，在DFS的时候要有vis数组标记被访问过的点，否则递归太深会爆空间，当时不断爆空间不知道干嘛了第一时间想到数组开大了，但是后来查看过别人的代码开的数组比我还大，后来才想到是递归的问题，很无语………然后就是构建邻接表，是只对MST里面的边构建邻接表，非安全边不要，就是这个原因也WA了很多次
- 另外这个代码没有考虑MST不连通的情况，但是也AC了。另外也没有考虑什么边的权值为0或者负值但是测试过简单的数据是没错的
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std; #define N 110 #define M 10010 struct edge { int u,v,w; }a[M],b[M]; struct mat {int k; int w;}; vector <struct mat> g[N]; int n,m,sumw; int mm; //收集所有非安全边在b边集数组，mm是非安全边的条数 int p[N]; //用于并查集 bool vis[N]; int FIND; //判断是否找到了可以替换的边 int cmp(struct edge x , struct edge y) { return x.w<y.w; } int find(int x) { return p[x]==x ? x : p[x]=find(p[x]); } void input() { int i,j,u,v,w; struct mat tmp; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) g[i].clear(); //初始化 for(i=1; i<=m; i++) scanf("%d%d%d",&a[i].u , &a[i].v , &a[i].w); return ; } void kruskal() { int i,j,x,y; struct mat tmp; sort(a+1,a+m+1,cmp); for(i=1 ;i<=n; i++) p[i]=i; mm=0; sumw=0; for(i=1; i<=m; i++) { x=find(a[i].u); y=find(a[i].v); if(x!=y) { //printf("(%d,%d)",a[i].u,a[i].v); sumw+=a[i].w; p[x]=y; tmp.w=a[i].w; tmp.k=a[i].v; g[a[i].u].push_back(tmp); tmp.k=a[i].u; g[a[i].v].push_back(tmp); //因为是无向边 } else b[++mm]=a[i]; } //printf("\n"); //printf("MST的总权值为%d\n",sumw); //printf("所有的非安全边 %d\n",mm); //for(i=1; i<=mm; i++) printf("%d %d %d\n",b[i].u,b[i].v,b[i].w); return ; } int dfs(int W , int u , int v) { int i,kk,tmp; vis[u]=1; if(u==v) return 1; for(i=0; i<g[u].size(); i++) { if( !vis[g[u][i].k] && (tmp=dfs(W,g[u][i].k,v)) ) { if(FIND) return 1; if(W==g[u][i].w) { FIND=1; //printf("找到的边为(%d,%d)%d\n",u,kk,g[u][i].w); } return 1; } } return 0; } void solve() { int i,j,kk,u,v,tmp,W; for(i=1; i<=mm; i++) //枚举所有的非安全边 { memset(vis,0,sizeof(vis)); u=b[i].u; v=b[i].v; W=b[i].w; vis[u]=1; FIND=0; tmp=dfs(W,u,v); if(FIND) break; //添加非安全边b[i]，从该边的u点开始dfs知道找到v点为止 //找到v点后返回， 返回时即环的路径，然后这一查看这些环的线段中是否有权等于W //dfs有3个参数，非安全边的权值W，要找的目标顶点v，和当前顶点u } if(i>mm) //找完了整个非安全边数组都不能证明MST不唯一，那说明MST是唯一的 printf("%d\n",sumw); else printf("Not Unique!\n"); } void printff() { int i,j,kk,w; printf("打印所有邻接表,注意这个邻接表是MST内的连通情况\n"); for(i=1; i<=n; i++) { printf("%d: ",i); for(j=0; j<g[i].size(); j++) printf("%d(%d) ",g[i][j].k,g[i][j].w); printf("\n"); } } int main() { int CASE; scanf("%d",&CASE); while(CASE--) { input(); kruskal(); //先单独构建出MST //printff(); solve(); } return 0; }