C++ 解法, 执行用时: 4ms, 内存消耗: 480KB, 提交时间: 2018-04-29

#include <stdio.h>  
#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;  
typedef struct Node  
{  
    int p;  
    int q;  
    int k;     
}node;  
   
vector<int> pre;  
int unionsearch(int index) {  
    while (pre[index] != index) {  
        pre[index] = pre[pre[index]];  
        index = pre[index];  
    }  
    return index;  
}  
void join(int x, int y) {  
    if (pre[x] != pre[y]) {  
        pre[x] = y;  
    }  
}  
bool cmp(const node& vn1, const node & vn2) {  
    return vn1.k < vn2.k;  
}  
int main(void) {  
    int N, M;  
    scanf("%d %d", &N, &M);  
    vector<node> vn;  
    for (int i = 0; i < M; i++) {  
        node tmp;  
        scanf("%d %d %d", &tmp.p, &tmp.q, &tmp.k);  
        vn.push_back(tmp);  
    }  
    // initialize union set;  
    for (int i = 0; i <= N; i++) {  
        pre.push_back(i);  
    }  
    sort(vn.begin(), vn.end(), cmp);  
    int res = 0;  
    for (int i = 0; i < M; i++) {  
        int rootA = unionsearch(vn[i].p);  
        int rootB = unionsearch(vn[i].q);  
        if (rootA != rootB) {  
            if (res < vn[i].k) {  
                res = vn[i].k;  
            }  
            join(rootA, rootB);  
        }  
    }  
    cout << res << endl;  
    return 0;  
}  

C++ 解法, 执行用时: 5ms, 内存消耗: 384KB, 提交时间: 2020-12-23

#include <cstdio>
#include <algorithm>

using namespace std;

static const int MAXN = 10003, MAXM = 1000003;

struct Edge{
	int a;
	int b;
	int w;	
    bool operator< (const Edge& e) const
	{
		return w < e.w;
	}
} edges[MAXM];

int parent[MAXN];

void add_edge(int a, int b, int w, int i)
{
	edges[i].a = a;
	edges[i].b = b;
	edges[i].w = w;
}

int find_parent(int n)
{
	if(parent[n] != n) parent[n] = find_parent(parent[n]);
	
	return parent[n];
}

int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		for(int i=0; i<m; ++i)
		{
			int a, b, w;
			scanf("%d %d %d", &a, &b, &w);
			add_edge(a, b, w, i);
		}
		sort(edges, edges+m);
		for(int i=1; i<=n; ++i)
			parent[i] = i;
		
		int ans = -1;
		for(int i=0; i<m; ++i)
		{
			int pa = find_parent(edges[i].a);
			int pb = find_parent(edges[i].b);
			if(pa != pb)
			{                
				parent[pa] = pb;
				if(edges[i].w > ans) ans = edges[i].w;
			}
		}
		printf("%d\n", ans);
	}
    return 0;
}