POJ 2421 Constructing Roads (Kruskal算法+压缩路径并查集 )

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct node
{
    int u;
    int v;
    int w;
    bool operator <(const node&x)const  //node类自己的运算符重载，这样在sort时，直接写就可以了，不用调用函数了
    {
        return w<x.w;   
    }
}q[5000];

int fa[105];
int findset(int x)
{
    return fa[x]!=x?fa[x]=findset(fa[x]):x;
} //带压缩路径的并查集

int main()
{
    int n, m;
    int u, v;
    int i, j;
    int dd;
    int e=0;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%d", &dd ); //因为是无向图，所以只需要存储一个上三角的数据或者下三角的数据就行，我存储的是上三角
            if(i<j)
            {
               q[e].u=i; q[e].v =j; q[e++].w=dd; //记录到结构体当中
            }
        }
    } //
    sort(q+0, q+e); //对结构体数组进行排序，边权小的靠前排序
    for(i=0; i<=n; i++)
    {
        fa[i]=i;  //并查集数组初始化，初始指向自己
    }
    scanf("%d", &m);  //读入m条边
    while(m--)
    {
        scanf("%d %d", &u, &v); 
        fa[findset(u)] = findset(v); //表示u和v已经有路径相同不需要再修建道路，所以在并茶几上把他们并到一个子集里
    }
    int ans=0; //用来记录最后还需要修建的路径总长度
    for(int k=0; k<e; k++)
    {
        if(findset(q[k].u)!=findset(q[k].v) ) //如果这个结构体元素存储的两条村庄不属于同一个子集
        {
            fa[fa[q[k].u]] = fa[q[k].v]; //把这村庄合并到一个子集里 或者称合并到一棵树上
            ans+=q[k].w;
        }
    }
    printf("%d\n", ans );  //此代码还可以时间上优化一下，就是从输入m条边开始就统计已经加入生成树的边数，定义一个计数变量，当计数变量的值==n-1时就可以跳出上面的循环了
    return 0;
}

import java.util.*;
import java.io.Reader;
import java.io.Writer;
import java.math.*; //导入java下的工具包

public class Main{
	public static void print(string x){  //输出最小生成树的边长和
		System.out.print(x);
	}
	static int[] fa; //并查集数组
	public static int findset(int x){
		return fa[x]!=x?fa[x]=findset(fa[x]):x; 
	} //带压缩路径的并查集
	public static void main(string[] argv){ //定义main函数的参数是一个字符串类型的数组argv
		Scanner input = new Scanner(System.in); //定义java的标准输入
		while(input.hasNextInt() ){ //多组测试
			int N = input.nextInt();
			int [][]p = new int [N+1][N+1]; //为邻接矩阵申请内存
			for(int i=0; i<n; i++)
			{
				for(int j=0; j<n; j++)
				{
					p[i][j] = input.nextInt();
				}
			}
			fa = new int[N+1]; //为并查集数组申请内存
			for(int i=0; i<N; i++) fa[i]=i;  //父节点指针指向自己 初始化
			for(int m=intput.nextInt(); m>0; m-- )
			{
				fa[findset(input.nextInt()-1)] = findset(input.nextInt()-1); //建立父子关系
			}
			int ans=0; //新建公路的长度初始化
			for(int k=1; k<=1000; k++)
			{
				for(int i=0; i<N; i++)
				{
					for(int j=0; j<N; j++)
					{
						if(p[i][j]==k && findset(i)!=findset(j) )
						{
							fa[fa[i]] = fa[j];
							ans+=k;
						}
					}
				}
			}
			print(ans+"\n");
		}
	}
}