洛谷3366最小生成树kruskal,c语言

题目描述

例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。

输入格式

第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。

接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。

输出格式

如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。

输入输出样例

输入 #1复制

4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3

输出 #1复制

7

说明/提示

数据规模：

对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。

对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。

对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。

对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。

#include #include #include #define max 200005 typedef struct graph {  int edga_first,edga_second;  int e; } Node; int arr[max],rank[max]; Node a[max]; int cmp(const void*a, const void *b) {  return ((Node*)a)->e - ((Node*)b)->e; } void Init(int n) {  for(int i=1; i<=n; i  )  {   arr[i]=i;   rank[i]=1;  } } int find(int x) {  if(x==arr[x])  {   return x;  }  else  {   return arr[x]=find(arr[x]);  } } void unite(int x,int y) {  x=find(x);  y=find(y);  if(x==y)  {   return;  }  if(rank[x]