无向图最小生成树

无向图最小生成树

N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。 Input第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)Output输出最小生成树的所有边的权值之和。Sample Input

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

Sample Output

37

思路：我是用并差集写的，把权值从小到大排好序，再建立成树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int x,y,cn;
};
bool cmp(node n,node m)
{
    return n.cn<m.cn;
}
int f[100000];
int find(int x)
{
    int r=x;
    while(f[r]!=r)
    {
        r=f[r];
    }
    return r;
}
int merge(node n)
{
    int xx=find(n.x);
    int yy=find(n.y);
    if(xx!=yy)
    {
        f[xx]=yy;
        return 1;
    }
    return 0;
}
int main()
{
    struct node std[50010];
    int n,i,m,j,k,t;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&std[i].x,&std[i].y,&std[i].cn);
        }
        sort(std+1,std+m+1,cmp);
        for(i=1;i<=n;i++)
        {
            f[i]=i;
        }
        int num=0,sum=0;
        for(i=1;i<=m&&num<=n-1;i++)
        {
            if(merge(std[i])==1)
               {
                   num++;
                   sum+=std[i].cn;
               }
        }
        printf("%d\n",sum);
    }
    return 0;
}