题目描述

blablabla

#include<stdio.h>
#include<stdbool.h>

#define N 1010
#define M 110

int n, e;
int fa[M];

struct edge{
    int a, b;
    int w;
    bool isMST;
}edges[N];

void quick_sort(struct edge edges[], int l, int r){
    if(l >= r)  return;
    int x = edges[(l+r)/2].w, i = l - 1, j = r + 1;

    while(i < j){
        do i++;  while(edges[i].w < x);
        do j--;  while(edges[j].w > x);
        if(i < j){
            struct edge temp = edges[i];
            edges[i] = edges[j];
            edges[j] = temp;
        }
    }

    quick_sort(edges, l, j);
    quick_sort(edges, j+1, r);
}

int find(int x){  return  x == fa[x] ? x : (fa[x] = find(fa[x]));  }

int main(){

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

    for(int i = 1; i <= e; i++){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        if(a > b){
            edges[i].a = b;
            edges[i].b = a;
        }
        else{
            edges[i].a = a;
            edges[i].b = b;
        }
        edges[i].w = w;
        edges[i].isMST = false;
    }

    quick_sort(edges, 1, e);

    for(int i = 1; i <= n; i++)  fa[i] = i;

    for(int i = 1; i <= e; i++){
        int a = edges[i].a, b = edges[i].b;

        a = find(a), b = find(b);
        if(a != b){
            fa[a] = b;
            edges[i].isMST = true;
        }
    }

    for(int i = 1; i <= e; i++)
        if(edges[i].isMST) 
            printf("%d %d\n", edges[i].a, edges[i].b);

    return 0;
}