K - The Unique MST

K - The Unique MST

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct nond{

    int x,y,z;

}edge[*];

int T,N,M,x,y,z,fa[],num,ans[];

int tot,bns,k,answer=;

int cmp(nond aa,nond bb){

    return aa.z<bb.z;

}

int find(int x){

    return fa[x]==x?x:fa[x]=find(fa[x]);

}

int main(){

    cin>>T;

    while(T--){

        cin>>N>>M;

        tot=;bns=;

        answer=;

        memset(fa,,sizeof(fa));

        memset(ans,,sizeof(ans));

        for(int i=;i<=M;i++){

            cin>>x>>y>>z;

            edge[i].x=x;

            edge[i].y=y;

            edge[i].z=z;

        }

        sort(edge+,edge++M,cmp);

        for(int i=;i<=N;i++)    fa[i]=i;

        for(int i=;i<=M;i++){

            int dx=find(edge[i].x),dy=find(edge[i].y);

            if(dx!=dy){

                fa[dx]=dy;

                tot++;

                ans[tot]=i;

                bns+=edge[i].z;

            }

            if(tot==N-)    break;

        }

        for(int i=;i<=tot;i++){

            k=;num=;

            for(int j=;j<=N;j++)    fa[j]=j;

            sort(edge+,edge++M,cmp);

            for(int j=;j<=M;j++){

                if(j==ans[i])    continue;

                int dx=find(edge[j].x),dy=find(edge[j].y);

                if(dx!=dy){

                    fa[dx]=dy;

                    num++;

                    k+=edge[j].z;

                }

                if(num==N-)    break;

            }

            if(num==N-) answer=min(k,answer);

        }

        if(answer==bns)    cout<<"Not Unique!"<<endl;

        else    cout<<bns<<endl;

    }

}