判断最小生成树是否唯一 POJ --- 1679

网上两种算法对应都有:
题目链接

prim算法判最小生成树是否唯一

下面是这道题的AC代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=105;
const int inf=1e9;
int cas=1;
int n,m;
int mapp[maxn][maxn],vis[maxn],dis[maxn];
void prim(int u)
{
    CLR(vis);
    int flag=0,sum=0;
    for(int i=1;i<=n;i++)
        dis[i]=mapp[u][i];
    vis[u]=1;
    for(int i=1;i<=n;i++){
        int minn=inf;
        int v=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j] && minn>dis[j]){
                v = j;
                minn = dis[j];
            }
        }
        if(v!=-1){   //如果v=-1了,说明这个图已经连通了,不用再判断下去了,当然也可以直接break掉,一样的.
            //printf("%d %d\n",v,minn);
            int ans=0;   //记录相同权值的边有几条,把图画出来就懂的起了!!!
            for(int j=1;j<=n;j++){
                if(vis[j] && mapp[v][j] == minn)   //这一步处理的非常好.
                    ans++;
            }
            if(ans>1){    //如果大于1,说明用其他路也能达到该点,所以树就不唯一了,所以可以直接break了.
                flag=1;
                break;
            }
            sum+=minn;
            vis[v]=1;
            for(int j=1;j<=n;j++){
                if(!vis[j] && dis[j] > mapp[v][j])
                    dis[j] = mapp[v][j];
            }
        }
    }
    if(flag)
        printf("Not Unique!\n");
    else
        printf("%d\n",sum);
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) mapp[i][j]=0;
                else mapp[i][j]=inf;
            }
        }
        for(int i=0;i<m;i++){
            int u,v,w;
            cin >> u >> v >> w;
            mapp[u][v] = mapp[v][u] = w;
        }
        prim(1);   //从点 1 开始找.
    }
}

kruskal的算法,再用这个算法时有一点要特别注意,否则会一直WA,就是在进行删边操作时,注意删完或需要判断这个图是否是一个树!!!，如果不是的话返回-1或最大值,不要返回sum值,因为删去边后没有树的话,则最小生成树还是唯一的!!!
AC代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn = 1e5+5;
int pre[105];
int n,m;
vector<int>used;
struct node{ int u,v,w;} s[maxn];
void init(){ for(int i=0;i<=n;i++) pre[i]=i; }
int Find(int x){ return pre[x]==x?x:pre[x]=Find(pre[x]); }
bool cmp(node a,node b){ return a.w<b.w; }
int kruskal(int flag)
{
    int num=0;
    int sum=0;
    for(int i=0;i<m;i++){
        if(i==flag) continue;
        int u=Find(s[i].u);
        int v=Find(s[i].v);
        if( u != v){
            pre[v]=u;
            sum+=s[i].w;
            num++;
            if(flag==-1)
                used.push_back(i);
        }
        if(num==n-1)
            break;
    }
    int cnt=0;    //一定判断一下树是否联通!!!
    for(int i=1;i<=n;i++){
        if(pre[i]==i)
            cnt++;
    }
    if(cnt>1)
        return -1;
    return sum;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        CLR(s);
        scanf("%d %d",&n,&m);
        init();
        used.clear();     //不要忘了清空!!!
        for(int i=0;i<m;i++){
            scanf("%d %d %d",&s[i].u,&s[i].v,&s[i].w);
        }
        sort(s,s+m,cmp);
        int ans=kruskal(-1);
        int flag=0;
        for(int i=0;i<used.size();i++){
            init();
            int p=0;
            p=kruskal(used[i]);
            if(p==ans){
                flag=1;
                break;
            }
        }
        if(flag)
            printf("Not Unique!\n");
        else
            printf("%d\n",ans);
    }
}