poj 1679 The Unique MST 判断最小生成树是否唯一（图论）

借用的是Kruskal的并查集，算法中的一点添加和改动。

通过判定其中有多少条可选的边，然后跟最小生成树所需边做比较，可选的边多于所选边，那么肯定方案不唯一。

如果不知道这个最小生成树的算法，还是先去理解下这个算法的原理，再继续看。

多加的几行与cnt2很类似的cnt1统计，是统计当前未选边中相同长度的边还有哪些可以选，但不标记，只是为了把当前可选的边全部统计出来。

其他细节，自己要细心点～

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 #include <iostream>

 #include <algorithm>

 #include <climits>

 #include <queue>

 using namespace std;

 //Kruskal算法 求最小生成树是否唯一

 const int MAX = ;

 int F[MAX];

 struct Edge

 {

     int u,v,w;

 } edge[MAX*MAX];

 int tol;

 void addedge(int u,int v,int w)

 {

     edge[tol].u = u;

     edge[tol].v = v;

     edge[tol++].w = w;

 }

 bool cmp(Edge a,Edge b)

 {

     return a.w < b.w;

 }

 int find(int x)

 {

     if(F[x] == -) return x;

     else return F[x] = find(F[x]);

 }

 void Kruskal(int n)

 {

     memset(F,-,sizeof(F));

     sort(edge,edge+tol,cmp);

     int cnt1 = ,cnt2 =  ;

     int ans = ;

     for(int i = ; i < tol; )

     {

         int j = i;

         while(j < tol && edge[j].w == edge[i].w)

         {

             int u = edge[j].u;

             int v = edge[j].v;

             int t1 = find(u);

             int t2 = find(v);

             if(t1 != t2)

             {

                 cnt1++;

             }

             j++;

         }

         j = i;

         while(j < tol && edge[j].w == edge[i].w)

         {

             int u = edge[j].u;

             int v = edge[j].v;

             int w = edge[j].w;

             int t1 = find(u);

             int t2 = find(v);

             if(t1 != t2)

             {

                 ans += w;

                 F[t1] = t2;

                 cnt2++;

             }

             j++;

         }

         i = j;

         if(cnt2 == n - )

             break;

     }

     //printf("%d %d\n",cnt1,cnt2);

     if(cnt1 > cnt2 || cnt2 != n -)

         printf("Not Unique!\n");

     else

         printf("%d\n",ans);

 }

 int main(void)

 {

     int t,m,n,i,x,y,w;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d %d",&n,&m);

         tol = ;

         for(i = ; i < m; i++)

         {

             scanf("%d %d %d",&x,&y,&w);

             addedge(x,y,w);

         }

         Kruskal(n);

     }

     return ;

 }