poj 1679 The Unique MST

http://poj.org/problem?id=167 9
최소 생 성 트 리 유일 하 냐 고   사실 작은 생 성 트 리 가 최소 생 성 트 리 인지 물 어 보 는 거 예요.
생각:
1  Kruskal 최소 생 성 트 리 MIN 은 어떤 변 을 사 용 했 는 지, 어떤 변 을 사 용 했 는 지 기록 하고 나 무 를 만 들 지 않 습 니 다.
2  dfs 는 모든 점 에서 최소 생 성 트 리 의 임의의 두 점 사이 의 가장 긴 변 을 구하 기 시작 합 니 다.
3. 사용 하지 않 은 사 이 드 가입 의 경우 취 합 니 다 (MIN + 이 사 이 드 권 - 트 리 중 이 두 점 사이 의 최 장 사 이 드 권) 가장 작은 것 은 작은 생 성 트 리 입 니 다.
코드 및 설명:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<map>

#include<queue>

#include<cmath>

#define LL long long



using namespace std;



const int N=105;



struct node

{

    struct tt *next;

}mem[N];

struct tt

{

    int j,k;

    struct tt *next;

};

struct ss

{

    bool used;

    int i,j,d;

}side[N*N];

int Mi_j[N][N];

int f[N];

void build(int i,int j,int d)//  

{

    struct tt *t=new tt;

    t->j=j;

    t->k=d;

    t->next=mem[i].next;

    mem[i].next=t;

}

void Dele(int n)//  

{

    for(int i=1;i<=n;++i)

    mem[i].next=NULL;

}

inline int findx(int x)//   

{

    if(f[x]!=x)

    f[x]=findx(f[x]);

    return f[x];

}

int Kruskal(int n,int m)//      

{

    int sum=0;

    for(int i=1;i<=n;++i)

    f[i]=i;

    for(int l=0;l<m;++l)

    {

        int x=side[l].i;

        int y=side[l].j;

        if(findx(x)!=findx(y))

        {

            build(x,y,side[l].d);//  

            build(y,x,side[l].d);

            f[findx(x)]=y;

            sum+=side[l].d;

            side[l].used=true;//      

        }

    }

    return sum;

}

void dfs(int st,int x,int pre,int M)

{

    if(M!=0)

    Mi_j[st][x]=max(Mi_j[st][x],M);// st x    

    struct tt *t=mem[x].next;

    while(t!=NULL)

    {

        if(t->j!=pre)

        {

            dfs(st,t->j,x,max(M,t->k));

        }

        t=t->next;

    }

}

int Fmtree(int n,int m,int MIN)

{

    int mtree=MIN+1;

    memset(Mi_j,0,sizeof(Mi_j));

    for(int i=1;i<=n;++i)

    dfs(i,i,0,0);//             

    for(int l=0;l<m;++l)

    {

        if(side[l].used==true)

        continue;

        int x=side[l].i;

        int y=side[l].j;

        mtree=min(mtree,MIN+side[l].d-Mi_j[x][y]);//  

    }

    return mtree;

}

int main()

{

    //freopen("data.txt","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

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

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

        {

            scanf("%d %d %d",&side[i].i,&side[i].j,&side[i].d);

            side[i].used=false;

        }

        int MIN=Kruskal(n,m);

        if(MIN==Fmtree(n,m,MIN))

        printf("Not Unique!
");

        else

        printf("%d
",MIN);

        Dele(n);

    }

    return 0;

}