修路方案 Kruskal 之 次小生成树

次小生成树 : Kruskal 是先求出来  最小生成树 , 并且记录下来所用到的的边 , 然后再求每次都 去掉最小生成树中的一个边 , 这样求最小生成树 , 然后看能不能得到 和原来最小生成树一样的消耗 , 如果能的话就有次小生成树

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<iostream>

#include<limits.h>

#include<algorithm>

#include<queue>

#include<vector>

#include<set>

#include<stack>

#include<string>

#include<sstream>

#include<map>

#include<cctype>

using namespace std;

int n,m,minn,father[],sum,visited[];

struct node

{

    int x,y,l;

}a[];

bool cmp(node a,node b)

{

    return a.l<b.l;

}

void init(int length)

{

    for(int i=;i<=length;i++)

    {

        father[i]=i;

    }

}

int find(int x)                      //  做了时间上的优化 ,但是 在空间复杂度上比较高

{

    if(x!=father[x])

        father[x]=find(father[x]);

    sum++;

    return father[x];

}

bool merge(int x,int y)    // 做了时间复杂度上的优化  让并查集的 深度尽量  浅

{

    int sum1,sum2;

    sum=;

    x=find(x);

    sum1=sum;        //    x  的深度

    sum=;

    y=find(y);

    sum2=sum;       //    y   的深度

    if(x!=y)

    {

        if(sum1>sum2)

            father[y]=x;

        else

            father[x]=y;

        return true;

    }

    else

        return false;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

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

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

        {

            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);

        }

        init(n);

        sort(a,a+m,cmp);  // 数据的收集,排序和并查集的初始化已经完成

        int count1=minn=;

        memset(visited,,sizeof(visited));

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

        {

            if(merge(a[i].x,a[i].y))

            {

                count1++;

                minn+=a[i].l;   //最小生成树的 费用 已经知道了

                visited[i]=;   //  第 i 条边已经使用过了 .

            }

            if(count1==n-)   //  已经有了 n-1条边

                break;

        }

        int flag=;

        for(int j=;j<m;j++)

        {

            if(visited[j])

            {

                int q=j,tem=,count1=;

                init(n);

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

                {

                    if(i!=q&&merge(a[i].x,a[i].y))

                    {

                        count1++;

                        tem+=a[i].l;   //最小生成树的 费用 已经知道了

                    }

                    if(count1==n-)

                    {

                        if(tem==minn)

                            flag=;

                        break;

                    }

                }

            }

            if(flag==)

                break;

        }

        if(flag==)

            printf("Yes\n");

        else

            printf("No\n");

    }

    return ;

}