程式碼備份區

題意：

現在有一個新的Minimum Spanning Tree的方法是：如果有環的話，每次找最大的那個邊移除掉，直到沒有環為止

問說被拔掉的邊有哪些，按照大小輸出

解法：

直接用Kruskal's Algorithm作MST，如果不是MST的edge就表示他是會被拔掉的，就輸出

程式碼：

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

int n,m;
int set[123456];
int e[123456][3];
int cmp(const void*a,const void*b){
    int *p = (int*)a;
    int *q = (int*)b;
    return p[2]-q[2];
}
int findSet(int now){
    if(set[now]!=now)set[now] = findSet(set[now]);
    return set[now];
}
int main(){
    int i;
    int f;
    int setA,setB;
    while(scanf("%d %d",&n,&m)!=EOF&&(n|m)){
        for(i=0;i<n;++i)set[i] = i;
        for(i=0;i<m;++i){
            scanf("%d %d %d",&e[i][0],&e[i][1],&e[i][2]);
        }
        qsort(e,m,sizeof(e[0]),cmp);
        for(i=f=0;i<m;++i){
            setA = findSet(e[i][0]);
            setB = findSet(e[i][1]);
            if(setA != setB){
                set[setA] = setB;
            }else {
                if(f)printf(" ");
                else f = 1;
                printf("%d",e[i][2]);
            }
        }
        if(!f)printf("forest");
        puts("");
    }

    return 0;
}